1ECM(1) ECM(1)
2
6 ecm - integer factorization using ECM, P-1 or P+1
7
9 ecm [options] B1 [B2min-B2max | B2]
10
13 ecm is an integer factoring program using the Elliptic Curve Method
14 (ECM), the P-1 method, or the P+1 method. The following sections
15 describe parameters relevant to these algorithms.
16
18 B1
19 B1 is the step 1 bound. It is a mandatory parameter. It can be
20 given either in integer format (for example 3000000) or in
21 floating-point format (3000000.0 or 3e6). The largest possible B1
22 value is 9007199254740996 for P-1, and ULONG_MAX or
23 9007199254740996 (whichever is smaller) for ECM and P+1. All primes
24 2 <= p <= B1 are processed in step 1.
25 B2
27 B2 is the step 2 bound. It is optional: if omitted, a default value
28 is computed from B1, which should be close to optimal. Like B1, it
29 can be given either in integer or in floating-point format. The
30 largest possible value of B2 is approximately 9e23, but depends on
31 the number of blocks k if you specify the -k option. All primes B1
32 <= p <= B2 are processed in step 2. If B2 < B1, no step 2 is
33 performed.
34 B2min-B2max
36 alternatively one may use the B2min-B2max form, which means that
37 all primes B2min <= p <= B2max should be processed. Thus specifying
38 B2 only corresponds to B1-B2. The values of B2min and B2max may be
39 arbitrarily large, but their difference must not exceed
40 approximately 9e23, subject to the number of blocks k.
41
43 -pm1
44 Perform P-1 instead of the default method (ECM).
45 -pp1
47 Perform P+1 instead of the default method (ECM).
48
50 -x0 x
51 [ECM, P-1, P+1] Use x (arbitrary-precision integer or rational) as
52 initial point. For example, -x0 1/3 is valid. If not given, x is
53 generated from the sigma value for ECM, or at random for P-1 and
54 P+1.
55 -param i
57 [ECM] Use i as curve parametrization.
58 -sigma s
60 [ECM] Use s (arbitrary-precision integer) as curve generator, can
61 use -sigma i:s to specify -param i at the same time.
62 If omitted, s is generated at random.
63 -A a
65 [ECM] Use a (arbitrary-precision integer) as curve parameter. If
66 omitted, is it generated from the sigma value.
67 -go val
69 [ECM, P-1, P+1] Multiply the initial point by val, which can any
70 valid expression, possibly containing the special character N as
71 place holder for the current input number. Example:
72 ecm -pp1 -go "N^2-1" 1e6 < composite2000
74
77 -k k
78 [ECM, P-1, P+1] Perform k blocks in step 2. For a given B2 value,
79 increasing k decreases the memory usage of step 2, at the expense
80 of more cpu time.
81 -treefile file
83 Stores some tables of data in disk files to reduce the amount of
84 memory occupied in step 2, at the expense of disk I/O. Data will be
85 written to files file.1, file.2 etc. Does not work with fast stage
86 2 for P+1 and P-1.
87 -power n
89 [ECM] Use x^n for Brent-Suyama's extension (-power 1 disables
90 Brent-Suyama's extension). The default polynomial is chosen
91 depending on the method and B2.
92 -dickson n
94 [ECM] Use degree-n Dickson's polynomial for Brent-Suyama's
95 extension.
96 -maxmem n
98 Use at most n megabytes of memory in stage 2.
99 -ntt, -no-ntt
101 Enable or disable the Number-Theoretic Transform code for
102 polynomial arithmetic in stage 2. With NTT, dF is chosen to be a
103 power of 2, and is limited by the number suitable primes that fit
104 in a machine word (which is a limitation only on 32 bit systems).
105 The -no-ntt variant uses more memory, but is faster than NTT with
106 large input numbers. By default, NTT is used for P-1, P+1 and for
107 ECM on numbers of size at most 30 machine words.
108
110 -q
111 Quiet mode. Found factorizations are printed on standard output,
112 with factors separated by white spaces, one line per input number
113 (if no factor was found, the input number is simply copied).
114 -v
116 Verbose mode. More information is printed, more -v options increase
117 verbosity. With one -v, the kind of modular multiplication used,
118 initial x0 value, step 2 parameters and progress, and expected
119 curves and time to find factors of different sizes for ECM are
120 printed. With -v -v, the A value for ECM and residues at the end of
121 step 1 and step 2 are printed. More -v print internal data for
122 debugging.
123 -timestamp
125 Print a time stamp whenever a new ECM curve or P+1 or P-1 run is
126 processed.
127
129 Several algorithms are available for modular multiplication. The
130 program tries to find the best one for each input; one can force a
131 given method with the following options.
132 -mpzmod
134 Use GMP's mpz_mod function (sub-quadratic for large inputs, but
135 induces some overhead for small ones).
136 -modmuln
138 Use Montgomery's multiplication (quadratic version). Usually best
139 method for small input.
140 -redc
142 Use Montgomery's multiplication (sub-quadratic version).
143 Theoretically optimal for large input.
144 -nobase2
146 Disable special base-2 code (which is used when the input number is
147 a large factor of 2^n+1 or 2^n-1, see -v).
148 -base2 n
150 Force use of special base-2 code, input number must divide 2^n+1 if
151 n > 0, or 2^|n|-1 if n < 0.
152
154 The following options enable one to perform step 1 and step 2
155 separately, either on different machines, at different times, or using
156 different software (in particular, George Woltman's Prime95/mprime
157 program can produce step 1 output suitable for resuming with GMP-ECM).
158 It can also be useful to split step 2 into several runs, using the
159 B2min-B2max option.
160 -inp file
162 Take input from file file instead of from standard input.
163 -save file
165 Save result of step 1 in file. If file exists, an error is raised.
166 Example: to perform only step 1 with B1=1000000 on the composite
167 number in the file "c155" and save its result in file "foo", use
168 ecm -save foo 1e6 1 < c155
170 -savea file
173 Like -save, but appends to existing files.
174 -resume file
176 Resume residues from file, reads from standard input if file is
177 "-". Example: to perform step 2 following the above step 1
178 computation, use
179 ecm -resume foo 1e6
181 -chkpnt file
184 Periodically write the current residue in stage 1 to file. In case
185 of a power failure, etc., the computation can be continued with the
186 -resume option.
187 ecm -chkpnt foo -pm1 1e10 < largenumber.txt
189
192 The “loop mode” (option -c n) enables one to run several curves on each
193 input number. The following options control its behavior.
194 -c n
196 Perform n runs on each input number (default is one). This option
197 is mainly useful for P+1 (for example with n=3) or for ECM, where n
198 could be set to the expected number of curves to find a d-digit
199 factor with a given step 1 bound. This option is incompatible with
200 -resume, -sigma, -x0. Giving -c 0 produces an infinite loop until a
201 factor is found.
202 -one
204 In loop mode, stop when a factor is found; the default is to
205 continue until the cofactor is prime or the specified number of
206 runs are done.
207 -b
209 Breadth-first processing: in loop mode, run one curve for each
210 input number, then a second curve for each one, and so on. This is
211 the default mode with -inp.
212 -d
214 Depth-first processing: in loop mode, run n curves for the first
215 number, then n curves for the second one and so on. This is the
216 default mode with standard input.
217 -ve n
219 In loop mode, in the second and following runs, output only
220 expressions that have at most n characters. Default is -ve 0.
221 -i n
223 In loop mode, increment B1 by n after each curve.
224 -I n
226 In loop mode, multiply B1 by a factor depending on n after each
227 curve. Default is one which should be optimal on one machine, while
228 -I 10 could be used when trying to factor the same number
229 simultaneously on 10 identical machines.
230
232 These optins allow for executing shell commands to supplement
233 functionality to GMP-ECM.
234 -prpcmd cmd
236 Execute command cmd to test primality if factors and cofactors
237 instead of GMP-ECM´s own functions. The number to test is passed
238 via stdin. An exit code of 0 is interpreted as “probably prime”, a
239 non-zero exit code as “composite”.
240 -faccmd cmd
242 Executes command cmd whenever a factor is found by P-1, P+1 or ECM.
243 The input number, factor and cofactor are passed via stdin, each on
244 a line. This could be used i.e. to mail new factors automatically:
245 ecm -faccmd ´mail -s “$HOSTNAME found a factor”
247 me@myaddress.com´ 11e6 < cunningham.in
248 -idlecmd cmd
251 Executes command cmd before each ECM curve, P-1 or P+1 attempt on a
252 number is started. If the exit status of cmd is non-zero, GMP-ECM
253 terminates immediately, otherwise it continues normally. GMP-ECM is
254 stopped while cmd runs, offering a way for letting GMP-ECM sleep
255 for example while the system is otherwise busy.
256
258 -n
259 Run the program in “nice” mode (below normal priority).
260 -nn
262 Run the program in “very nice” mode (idle priority).
263 -primetest
265 perform a primality test on input, exits 0 if input is prime (or
266 PRP for large inputs).
267 -B2scale f
269 Multiply the default step 2 bound B2 by the floating-point value f.
270 Example: -B2scale 0.5 divides the default B2 by 2.
271 -stage1time n
273 Add n seconds to stage 1 time. This is useful to get correct
274 expected time with -v if part of stage 1 was done in another run.
275 -cofdec
277 Force cofactor output in decimal (even if expressions are used).
278 -h, --help
280 Display a short description of ecm usage, parameters and command
281 line options.
282 -printconfig
284 Prints configuration parameters used for the compilation and exits.
285
287 The input numbers can have several forms:
288 Raw decimal numbers like 123456789.
290 Comments can be placed in the file: everything after “//” is ignored,
292 up to the end of line.
293 Line continuation. If a line ends with a backslash character “\”, it is
295 considered to continue on the next line.
296 Common arithmetic expressions can be used. Example: 3*5+2^10.
298 Factorial: example 53!.
300 Multi-factorial: example 15!3 means 15*12*9*6*3.
302 Primorial: example 11# means 2*3*5*7*11.
304 Reduced primorial: example 17#5 means 5*7*11*13*17.
306 Functions: currently, the only available function is Phi(x,n).
308
310 The exit status reflects the result of the last ECM curve or P-1/P+1
311 attempt the program performed. Individual bits signify particular
312 events, specifically:
313 Bit 0
315 0 if normal program termination, 1 if error occurred
316 Bit 1
318 0 if no proper factor was found, 1 otherwise
319 Bit 2
321 0 if factor is composite, 1 if factor is a probable prime
322 Bit 3
324 0 if cofactor is composite, 1 if cofactor is a probable prime
325 Thus, the following exit status values may occur:
327 0
329 Normal program termination, no factor found
330 1
332 Error
333 2
335 Composite factor found, cofactor is composite
336 6
338 Probable prime factor found, cofactor is composite
339 8
341 Input number found
342 10
344 Composite factor found, cofactor is a probable prime
345 14
347 Probable prime factor found, cofactor is a probable prime
348
350 Report bugs on <https://gitlab.inria.fr/zimmerma/ecm>.
351
353 Pierrick Gaudry <gaudry at lix dot polytechnique dot fr> contributed
354 efficient assembly code for combined mul/redc;
355 Jim Fougeron <jfoug at cox dot net> contributed the expression parser
357 and several command-line options;
358 Laurent Fousse <laurent at komite dot net> contributed the middle
360 product code, the autoconf/automake tools, and is the maintainer of the
361 Debian package;
362 Alexander Kruppa <(lastname)al@loria.fr> contributed estimates for
364 probability of success for ECM, the new P+1 and P-1 stage 2 (with P.-L.
365 Montgomery), new AMD64 asm mulredc code, and some other things;
366 Dave Newman <david.(lastname)@jesus.ox.ac.uk> contributed the
368 Kronecker-Schoenhage and NTT multiplication code;
369 Jason S. Papadopoulos contributed a speedup of the NTT code
371 Paul Zimmermann <zimmerma at loria dot fr> is the author of the first
373 version of the program and chief maintainer of GMP-ECM.
374 Note: email addresses have been obscured, the required substitutions
376 should be obvious.
377 ECM(1)