1ECM(1) April 22, 2003 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 -sigma s
57 [ECM] Use s (arbitrary-precision integer) as curve generator. If
58 omitted, s is generated at random.
59 -A a
61 [ECM] Use a (arbitrary-precision integer) as curve parameter. If
62 omitted, is it generated from the sigma value.
63 -go val
65 [ECM, P-1, P+1] Multiply the initial point by val, which can any
66 valid expression, possibly containing the special character N as
67 place holder for the current input number. Example:
68 ecm -pp1 -go "N^2-1" 1e6 < composite2000
70
73 -k k
74 [ECM, P-1, P+1] Perform k blocks in step 2. For a given B2 value,
75 increasing k decreases the memory usage of step 2, at the expense
76 of more cpu time.
77 -treefile file
79 Stores some tables of data in disk files to reduce the amount of
80 memory occupied in step 2, at the expense of disk I/O. Data will be
81 written to files file.1, file.2 etc. Does not work with fast stage
82 2 for P+1 and P-1.
83 -power n
85 [ECM, P-1] Use x^n for Brent-Suyama´s extension (-power 1 disables
86 Brent-Suyama´s extension). The default polynomial is chosen
87 depending on the method and B2. For P-1 and P+1, disables the fast
88 stage 2. For P-1, n must be even.
89 -dickson n
91 [ECM, P-1] Use degree-n Dickson´s polynomial for Brent-Suyama´s
92 extension. For P-1 and P+1, disables the fast stage 2. Like for
93 -power, n must be even for P-1.
94 -maxmem n
96 Use at most n megabytes of memory in stage 2.
97 -ntt, -no-ntt
99 Enable or disable the Number-Theoretic Transform code for
100 polynomial arithmetic in stage 2. With NTT, dF is chosen to be a
101 power of 2, and is limited by the number suitable primes that fit
102 in a machine word (which is a limitation only on 32 bit systems).
103 The -no-ntt variant uses more memory, but is faster than NTT with
104 large input numbers. By default, NTT is used for P-1, P+1 and for
105 ECM on numbers of size at most 30 machine words.
106
108 -q
109 Quiet mode. Found factorizations are printed on standard output,
110 with factors separated by white spaces, one line per input number
111 (if no factor was found, the input number is simply copied).
112 -v
114 Verbose mode. More information is printed, more -v options increase
115 verbosity. With one -v, the kind of modular multiplication used,
116 initial x0 value, step 2 parameters and progress, and expected
117 curves and time to find factors of different sizes for ECM are
118 printed. With -v -v, the A value for ECM and residues at the end of
119 step 1 and step 2 are printed. More -v print internal data for
120 debugging.
121 -timestamp
123 Print a time stamp whenever a new ECM curve or P+1 or P-1 run is
124 processed.
125
127 Several algorithms are available for modular multiplication. The
128 program tries to find the best one for each input; one can force a
129 given method with the following options.
130 -mpzmod
132 Use GMP´s mpz_mod function (sub-quadratic for large inputs, but
133 induces some overhead for small ones).
134 -modmuln
136 Use Montgomery´s multiplication (quadratic version). Usually best
137 method for small input.
138 -redc
140 Use Montgomery´s multiplication (sub-quadratic version).
141 Theoretically optimal for large input.
142 -nobase2
144 Disable special base-2 code (which is used when the input number is
145 a large factor of 2^n+1 or 2^n-1, see -v).
146 -base2 n
148 Force use of special base-2 code, input number must divide 2^n+1 if
149 n > 0, or 2^|n|-1 if n < 0.
150
152 The following options enable one to perform step 1 and step 2
153 separately, either on different machines, at different times, or using
154 different software (in particular, George Woltman´s Prime95/mprime
155 program can produce step 1 output suitable for resuming with GMP-ECM).
156 It can also be useful to split step 2 into several runs, using the
157 B2min-B2max option.
158 -inp file
160 Take input from file file instead of from standard input.
161 -save file
163 Save result of step 1 in file. If file exists, an error is raised.
164 Example: to perform only step 1 with B1=1000000 on the composite
165 number in the file "c155" and save its result in file "foo", use
166 ecm -save foo 1e6 1 < c155
168 -savea file
171 Like -save, but appends to existing files.
172 -resume file
174 Resume residues from file, reads from standard input if file is
175 "-". Example: to perform step 2 following the above step 1
176 computation, use
177 ecm -resume foo 1e6
179 -chkpoint file
182 Periodically write the current residue in stage 1 to file. In case
183 of a power failure, etc., the computation can be continued with the
184 -resume option.
185 ecm -chkpnt foo -pm1 1e10 < largenumber.txt
187
190 The “loop mode” (option -c n) enables one to run several curves on each
191 input number. The following options control its behavior.
192 -c n
194 Perform n runs on each input number (default is one). This option
195 is mainly useful for P+1 (for example with n=3) or for ECM, where n
196 could be set to the expected number of curves to find a d-digit
197 factor with a given step 1 bound. This option is incompatible with
198 -resume, -sigma, -x0. Giving -c 0 produces an infinite loop until a
199 factor is found.
200 -one
202 In loop mode, stop when a factor is found; the default is to
203 continue until the cofactor is prime or the specified number of
204 runs are done.
205 -b
207 Breadth-first processing: in loop mode, run one curve for each
208 input number, then a second curve for each one, and so on. This is
209 the default mode with -inp.
210 -d
212 Depth-first processing: in loop mode, run n curves for the first
213 number, then n curves for the second one and so on. This is the
214 default mode with standard input.
215 -I n
217 In loop mode, multiply B1 by a factor depending on n after each
218 curve. Default is one which should be optimal on one machine, while
219 -I 10 could be used when trying to factor the same number
220 simultaneously on 10 identical machines.
221
223 These options allow for executing shell commands to supplement
224 functionality to GMP-ECM.
225
227 -stage1time n
228 Add n seconds to stage 1 time. This is useful to get correct
229 expected time with -v if part of stage 1 was done in another run.
230 -h, --help
232 Display a short description of ecm usage, parameters and command
233 line options.
234 -printconfig
236 Prints configuration parameters used for the compilation and exits.
237
239 The input numbers can have several forms:
240 Raw decimal numbers like 123456789.
242 Comments can be placed in the file: everything after “//” is ignored,
244 up to the end of line.
245 Line continuation. If a line ends with a backslash character “\”, it is
247 considered to continue on the next line.
248 Common arithmetic expressions can be used. Example: 3*5+2^10.
250 Factorial: example 53!.
252 Multi-factorial: example 15!3 means 15*12*9*6*3.
254 Primorial: example 11# means 2*3*5*7*11.
256 Reduced primorial: example 17#5 means 5*7*11*13*17.
258 Functions: currently, the only available function is Phi(x,n).
260
262 The exit status reflects the result of the last ECM curve or P-1/P+1
263 attempt the program performed. Individual bits signify particular
264 events, specifically:
265 Bit 0
267 0 if normal program termination, 1 if error occurred
268 Bit 1
270 0 if no proper factor was found, 1 otherwise
271 Bit 2
273 0 if factor is composite, 1 if factor is a probable prime
274 Bit 3
276 0 if cofactor is composite, 1 if cofactor is a probable prime
277 Thus, the following exit status values may occur:
279 0
281 Normal program termination, no factor found
282 1
284 Error
285 2
287 Composite factor found, cofactor is composite
288 6
290 Probable prime factor found, cofactor is composite
291 8
293 Input number found
294 10
296 Composite factor found, cofactor is a probable prime
297 14
299 Probable prime factor found, cofactor is a probable prime
300
302 Report bugs to <ecm-discuss@lists.gforge.inria.fr>, after checking
303 <http://www.loria.fr/~zimmerma/records/ecmnet.html> for bug fixes or
304 new versions.
305
307 Pierrick Gaudry <gaudry at lix dot polytechnique dot fr> contributed
308 efficient assembly code for combined mul/redc;
309 Jim Fougeron <jfoug at cox dot net> contributed the expression parser
311 and several command-line options;
312 Laurent Fousse <laurent at komite dot net> contributed the middle
314 product code, the autoconf/automake tools, and is the maintainer of the
315 Debian package;
316 Alexander Kruppa <(lastname)al@loria.fr> contributed estimates for
318 probability of success for ECM, the new P+1 and P-1 stage 2 (with P.-L.
319 Montgomery), new AMD64 asm mulredc code, and some other things;
320 Dave Newman <david.(lastname)@jesus.ox.ac.uk> contributed the
322 Kronecker-Schoenhage and NTT multiplication code;
323 Jason S. Papadopoulos contributed a speedup of the NTT code
325 Paul Zimmermann <zimmerma at loria dot fr> is the author of the first
327 version of the program and chief maintainer of GMP-ECM.
328 Note: email addresses have been obscured, the required substitutions
330 should be obvious.
331April 22, 2003 03/01/2013 ECM(1)