ECM(1) | April 22, 2003 | ECM(1) |

# NAME

ecm - integer factorization using ECM, P-1 or P+1

# SYNOPSIS

**ecm** [**options**] *B1*
[*B2min*-*B2max* | *B2*]

# DESCRIPTION

ecm is an integer factoring program using the Elliptic Curve Method (ECM), the P-1 method, or the P+1 method. The following sections describe parameters relevant to these algorithms.

# STEP 1 AND STEP 2 BOUND PARAMETERS

*B1*

*B1*is the step 1 bound. It is a mandatory parameter. It can be given either in integer format (for example 3000000) or in floating-point format (3000000.0 or 3e6). The largest possible

*B1*value is 9007199254740996 for P-1, and ULONG_MAX or 9007199254740996 (whichever is smaller) for ECM and P+1. All primes 2 <= p <=

*B1*are processed in step 1.

*B2*

*B2*is the step 2 bound. It is optional: if omitted, a default value is computed from

*B1*, which should be close to optimal. Like

*B1*, it can be given either in integer or in floating-point format. The largest possible value of

*B2*is approximately 9e23, but depends on the number of blocks

*k*if you specify the

**-k**option. All primes

*B1*<= p <=

*B2*are processed in step 2. If

*B2*<

*B1*, no step 2 is performed.

*B2min***-***B2max*

*B2min*-

*B2max*form, which means that all primes

*B2min*<= p <=

*B2max*should be processed. Thus specifying

*B2*only corresponds to

*B1*-

*B2*. The values of

*B2min*and

*B2max*may be arbitrarily large, but their difference must not exceed approximately 9e23, subject to the number of blocks

*k*.

# FACTORING METHOD

**-pm1**

**-pp1**

# GROUP AND INITIAL POINT PARAMETERS

**-x0 ***x*

*x*(arbitrary-precision integer or rational) as initial point. For example,

**-x0 1/3**is valid. If not given,

*x*is generated from the sigma value for ECM, or at random for P-1 and P+1.

**-sigma ***s*

*s*(arbitrary-precision integer) as curve generator. If omitted,

*s*is generated at random.

**-A ***a*

*a*(arbitrary-precision integer) as curve parameter. If omitted, is it generated from the sigma value.

**-go ***val*

*val*, which can any valid expression, possibly containing the special character N as place holder for the current input number. Example:

ecm -pp1 -go "N^2-1" 1e6 < composite2000

# STEP 2 PARAMETERS

**-k ***k*

*k*blocks in step 2. For a given

*B2*value, increasing

*k*decreases the memory usage of step 2, at the expense of more cpu time.

**-treefile ***file*

*file*.1,

*file*.2 etc. Does not work with fast stage 2 for P+1 and P-1.

**-power ***n*

*n*for Brent-Suyama's extension (

**-power 1**disables Brent-Suyama's extension). The default polynomial is chosen depending on the method and B2.

**-dickson ***n*

*n*Dickson's polynomial for Brent-Suyama's extension.

**-maxmem ***n*

*n*megabytes of memory in stage 2.

**-ntt**, **-no-ntt**

# OUTPUT

**-q**

**-v**

**-v**options increase verbosity. With one

**-v**, the kind of modular multiplication used, initial x0 value, step 2 parameters and progress, and expected curves and time to find factors of different sizes for ECM are printed. With

**-v -v**, the A value for ECM and residues at the end of step 1 and step 2 are printed. More

**-v**print internal data for debugging.

**-timestamp**

# MODULAR ARITHMETIC OPTIONS

Several algorithms are available for modular multiplication. The program tries to find the best one for each input; one can force a given method with the following options.

**-mpzmod**

**-modmuln**

**-redc**

**-nobase2**

**-v**).

**-base2** *n*

*n*+1 if

*n*> 0, or 2^|

*n*|-1 if

*n*< 0.

# FILE I/O

The following options enable one to perform step 1 and step 2
separately, either on different machines, at different times, or using
different software (in particular, George Woltman's Prime95/mprime program
can produce step 1 output suitable for resuming with GMP-ECM). It can also
be useful to split step 2 into several runs, using the *B2min-B2max*
option.

**-inp ***file*

*file*instead of from standard input.

**-save ***file*

*file*. If

*file*exists, an error is raised. Example: to perform only step 1 with

*B1*=1000000 on the composite number in the file "c155" and save its result in file "foo", use

ecm -save foo 1e6 1 < c155

**-savea ***file*

**-save**, but appends to existing files.

**-resume ***file*

*file*, reads from standard input if

*file*is "-". Example: to perform step 2 following the above step 1 computation, use

ecm -resume foo 1e6

**-chkpoint ***file*

*file*. In case of a power failure, etc., the computation can be continued with the

**-resume**option.

ecm -chkpnt foo -pm1 1e10 < largenumber.txt

# LOOP MODE

The “loop mode” (option **-c ***n*)
enables one to run several curves on each input number. The following
options control its behavior.

**-c ***n*

*n*runs on each input number (default is one). This option is mainly useful for P+1 (for example with

*n*=3) or for ECM, where

*n*could be set to the expected number of curves to find a d-digit factor with a given step 1 bound. This option is incompatible with

**-resume, -sigma, -x0**. Giving

**-c 0**produces an infinite loop until a factor is found.

**-one**

**-b**

**-inp**.

**-d**

*n*curves for the first number, then

*n*curves for the second one and so on. This is the default mode with standard input.

**-ve ***n*

*n*characters. Default is

**-ve 0**.

**-i ***n*

*B1*by

*n*after each curve.

**-I ***n*

*B1*by a factor depending on

*n*after each curve. Default is one which should be optimal on one machine, while

**-I 10**could be used when trying to factor the same number simultaneously on 10 identical machines.

# SHELL COMMAND EXECUTION

These optins allow for executing shell commands to supplement functionality to GMP-ECM.

**-prpcmd ***cmd*

*cmd*to test primality if factors and cofactors instead of GMP-ECM's own functions. The number to test is passed via stdin. An exit code of 0 is interpreted as “probably prime”, a non-zero exit code as “composite”.

**-faccmd ***cmd*

*cmd*whenever a factor is found by P-1, P+1 or ECM. The input number, factor and cofactor are passed via stdin, each on a line. This could be used i.e. to mail new factors automatically:

ecm -faccmd 'mail -s “$HOSTNAME found a factor” me@myaddress.com' 11e6 < cunningham.in

**-idlecmd ***cmd*

*cmd*before each ECM curve, P-1 or P+1 attempt on a number is started. If the exit status of

*cmd*is non-zero, GMP-ECM terminates immediately, otherwise it continues normally. GMP-ECM is stopped while

*cmd*runs, offering a way for letting GMP-ECM sleep for example while the system is otherwise busy.

# MISCELLANEOUS

**-n**

**-nn**

**-B2scale ***f*

*B2*by the floating-point value

*f*. Example:

**-B2scale 0.5**divides the default

*B2*by 2.

**-stage1time ***n*

*n*seconds to stage 1 time. This is useful to get correct expected time with

*-v*if part of stage 1 was done in another run.

**-cofdec**

**-h**, **--help**

**-printconfig**

# INPUT SYNTAX

The input numbers can have several forms:

Raw decimal numbers like 123456789.

Comments can be placed in the file: everything after “//” is ignored, up to the end of line.

Line continuation. If a line ends with a backslash character “\”, it is considered to continue on the next line.

Common arithmetic expressions can be used. Example:
*3*5+(2+7)^10*.

Factorial: example *53!*.

Multi-factorial: example *15!3* means 15*12*9*6*3.

Primorial: example *11#* means 2*3*5*7*11.

Reduced primorial: example *17#5* means 5*7*11*13*17.

Functions:

GCD(a,b): Greatest common divisor

Phi(n,x): n-th Cyclotomic Polynomial evaluated at x

# EXIT STATUS

The exit status reflects the result of the last ECM curve or P-1/P+1 attempt the program performed. Individual bits signify particular events, specifically:

Bit 0

Bit 1

Bit 2

Bit 3

Thus, the following exit status values may occur:

0

1

2

6

8

10

14

# BUGS

Report bugs on https://gitlab.inria.fr/zimmerma/ecm/.

# AUTHORS

Pierrick Gaudry <gaudry at lix dot polytechnique dot fr> contributed efficient assembly code for combined mul/redc;

Jim Fougeron <jfoug at cox dot net> contributed the expression parser and several command-line options;

Laurent Fousse <laurent at komite dot net> contributed the middle product code, the autoconf/automake tools, and is the maintainer of the Debian package;

Alexander Kruppa <(lastname)al@loria.fr> contributed estimates for probability of success for ECM, the new P+1 and P-1 stage 2 (with P.-L. Montgomery), new AMD64 asm mulredc code, and some other things;

Dave Newman <david.(lastname)@jesus.ox.ac.uk> contributed the Kronecker-Schoenhage and NTT multiplication code;

Jason S. Papadopoulos contributed a speedup of the NTT code

Paul Zimmermann <zimmerma at loria dot fr> is the author of the first version of the program and chief maintainer of GMP-ECM.

Note: email addresses have been obscured, the required substitutions should be obvious.

11/03/2023 | April 22, 2003 |