.\"Generated by db2man.xsl. Don't modify this, modify the source. .de Sh \" Subsection .br .if t .Sp .ne 5 .PP \fB\\$1\fR .PP .. .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Ip \" List item .br .ie \\n(.$>=3 .ne \\$3 .el .ne 3 .IP "\\$1" \\$2 .. .TH "ECM" 1 "" "" "" .SH NAME ecm \- integer factorization using ECM, P-1 or P+1 .SH "SYNOPSIS" .ad l .hy 0 .HP 4 \fBecm\fR [\fBoptions\fR] \fIB1\fR [\fB\fIB2min\fR\-\fIB2max\fR\fR | \fB\fIB2\fR\fR] .br .ad .hy .SH "DESCRIPTION" .PP 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\&. .SH "STEP 1 AND STEP 2 BOUND PARAMETERS" .TP \fI\fIB1\fR\fR \fIB1\fR 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 \fIB1\fR value is 9007199254740996 for P\-1, ULONG_MAX for ECM and P+1\&. All primes 2 <= p <= \fIB1\fR are processed in step 1\&. .TP \fI\fIB2\fR\fR \fIB2\fR is the step 2 bound\&. It is optional: if omitted, a default value is computed from \fIB1\fR, which should be close to optimal\&. Like \fIB1\fR, it can be given either in integer or in floating\-point format\&. The largest possible value of \fIB2\fR is approximately 9e23, but depends on the number of blocks \fIk\fR if you specify the \fB\-k\fR option\&. All primes \fIB1\fR <= p <= \fIB2\fR are processed in step 2\&. If \fIB2\fR < \fIB1\fR, no step 2 is performed\&. .TP \fI\fIB2min\fR\-\fIB2max\fR\fR alternatively one may use the \fIB2min\fR\-\fIB2max\fR form, which means that all primes \fIB2min\fR <= p <= \fIB2max\fR should be processed\&. Thus specifying \fIB2\fR only corresponds to \fIB1\fR\-\fIB2\fR\&. The values of \fIB2min\fR and \fIB2max\fR may be arbitrarily large, but their difference must not exceed approximately 9e23, subject to the number of blocks \fIk\fR\&. .SH "FACTORING METHOD" .TP \fB\-pm1\fR Perform P\-1 instead of the default method (ECM)\&. .TP \fB\-pp1\fR Perform P+1 instead of the default method (ECM)\&. .TP \fB\-t \fIn\fR\fR Perform trial division up to \fIn\fR, before P\-1, P+1 or ECM\&. In loop mode (see option \fB\-c\fR), trial division is only performed in the first run\&. .SH "GROUP AND INITIAL POINT PARAMETERS" .TP \fB\-x0 \fIx\fR\fR [ECM, P\-1, P+1] Use \fIx\fR (arbitrary\-precision integer or rational) as initial point\&. For example, \fB\-x0 1/3\fR is valid\&. If not given, \fIx\fR is generated from the sigma value for ECM, or at random for P\-1 and P+1\&. .TP \fB\-sigma \fIs\fR\fR [ECM] Use \fIs\fR (arbitrary\-precision integer) as curve generator\&. If omitted, \fIs\fR is generated at random\&. .TP \fB\-A \fIa\fR\fR [ECM] Use \fIa\fR (arbitrary\-precision integer) as curve parameter\&. If omitted, is it generated from the sigma value\&. .TP \fB\-go \fIval\fR\fR [ECM, P\-1, P+1] Multiply the initial point by \fIval\fR, which can any valid expression, possibly containing the special character N as place holder for the current input number\&. Example: .nf ecm \-pp1 \-go "N^2\-1" 1e6 < composite2000 .fi .SH "STEP 2 PARAMETERS" .TP \fB\-k \fIk\fR\fR [ECM, P\-1, P+1] Perform \fIk\fR blocks in step 2\&. For a given \fIB2\fR value, increasing \fIk\fR decreases the memory usage of step 2, at the expense of more cpu time\&. .TP \fB\-treefile \fIfile\fR\fR Stores some tables of data in disk files to reduce the amount of memory occupied in step 2, at the expense of disk I/O\&. Data will be written to files \fIfile\fR\&.1, \fIfile\fR\&.2 etc\&. .TP \fB\-power \fIn\fR\fR [ECM, P\-1] Use x^\fIn\fR for Brent\-Suyama's extension (\fB\-power 1\fR disables Brent\-Suyama's extension)\&. The default polynomial is chosen depending on the method and B2\&. For P\-1, \fIn\fR must be even\&. .TP \fB\-dickson \fIn\fR\fR [ECM, P\-1] Use degree\-\fIn\fR Dickson's polynomial for Brent\-Suyama's extension\&. Like for \fB\-power\fR, \fIn\fR must be even for P\-1\&. .TP \fB\-maxmem \fIn\fR\fR Use at most \fIn\fR megabytes of memory in stage 2\&. .TP \fB\-no\-ntt\fR Disable the Number\-Theoretic Transform code for polynomial arithmetic and allow free choice of dF\&. .SH "OUTPUT" .TP \fB\-q\fR Quiet mode\&. Found factorizations are printed on standard output, with factors separated by white spaces, one line per input number (if no factor was found, the input number is simply copied)\&. .TP \fB\-v\fR Verbose mode\&. More information is printed, more \fB\-v\fR options increase verbosity\&. With one \fB\-v\fR, 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 \fB\-v \-v\fR, the A value for ECM and residues at the end of step 1 and step 2 are printed\&. More \fB\-v\fR print internal data for debugging\&. .TP \fB\-timestamp\fR Print a time stamp whenever a new input number is processed\&. .SH "MODULAR ARITHMETIC OPTIONS" .PP 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\&. .TP \fB\-mpzmod\fR Use GMP's mpz_mod function (sub\-quadratic for large inputs, but induces some overhead for small ones)\&. .TP \fB\-modmuln\fR Use Montgomery's multiplication (quadratic version)\&. Usually best method for small input\&. .TP \fB\-redc\fR Use Montgomery's multiplication (sub\-quadratic version)\&. Theoretically optimal for large input\&. .TP \fB\-nobase2\fR Disable special base\-2 code (which is used when the input number is a large factor of 2^n+1 or 2^n\-1, see \fB\-v\fR)\&. .TP \fB\-base2\fR \fIn\fR Force use of special base\-2 code, input number must divide 2^\fIn\fR+1 if \fIn\fR > 0, or 2^|\fIn\fR|\-1 if \fIn\fR < 0\&. .SH "FILE I/O" .PP 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 \fIB2min\-B2max\fR option\&. .TP \fB\-inp \fIfile\fR\fR Take input from file \fIfile\fR instead of from standard input\&. .TP \fB\-save \fIfile\fR\fR Save result of step 1 in \fIfile\fR\&. If \fIfile\fR exists, an error is raised\&. Example: to perform only step 1 with \fIB1\fR=1000000 on the composite number in the file "c155" and save its result in file "foo", use .nf ecm \-save foo 1e6 1 < c155 .fi .TP \fB\-savea \fIfile\fR\fR Like \fB\-save\fR, but appends to existing files\&. .TP \fB\-resume \fIfile\fR\fR Resume residues from \fIfile\fR, reads from standard input if \fIfile\fR is "\-"\&. Example: to perform step 2 following the above step 1 computation, use .nf ecm \-resume foo 1e6 .fi .SH "LOOP MODE" .PP The ``loop mode'' (option \fB\-c \fIn\fR\fR) enables one to run several curves on each input number\&. The following options control its behavior\&. .TP \fB\-c \fIn\fR\fR Perform \fIn\fR runs on each input number (default is one)\&. This option is mainly useful for P+1 (for example with \fIn\fR=3) or for ECM, where \fIn\fR 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 \fB\-resume, \-sigma, \-x0\fR\&. Giving \fB\-c 0\fR produces an infinite loop until a factor is found\&. .TP \fB\-one\fR In loop mode, stop when a factor is found; the default is to continue until the cofactor is prime or the specified number of runs are done\&. .TP \fB\-b\fR Breadth\-first processing: in loop mode, run one curve for each input number, then a second curve for each one, and so on\&. This is the default mode with \fB\-inp\fR\&. .TP \fB\-d\fR Depth\-first processing: in loop mode, run \fIn\fR curves for the first number, then \fIn\fR curves for the second one and so on\&. This is the default mode with standard input\&. .TP \fB\-ve \fIn\fR\fR In loop mode, in the second and following runs, output only expressions that have at most \fIn\fR characters\&. Default is \fB\-ve 0\fR\&. .TP \fB\-i \fIn\fR\fR In loop mode, increment \fIB1\fR by \fIn\fR after each curve\&. .TP \fB\-I \fIn\fR\fR In loop mode, multiply \fIB1\fR by a factor depending on \fIn\fR after each curve\&. Default is one which should be optimal on one machine, while \fB\-I 10\fR could be used when trying to factor the same number simultaneously on 10 identical machines\&. .SH "SHELL COMMAND EXECUTION" .PP These optins allow for executing shell commands to supplement functionality to GMP\-ECM\&. .TP \fB\-prpcmd \fIcmd\fR\fR Execute command \fIcmd\fR 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''\&. .TP \fB\-faccmd \fIcmd\fR\fR Executes command \fIcmd\fR 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 automatically mail new factors: .nf ecm \-faccmd 'mail \-s ``$HOSTNAME found a factor'' me@myaddress\&.com' 11e6 < cunningham\&.in .fi .TP \fB\-idlecmd \fIcmd\fR\fR Executes command \fIcmd\fR before each ECM curve, P\-1 or P+1 attempt on a number is started\&. If the exit status of \fIcmd\fR is non\-zero, GMP\-ECM terminates immediately, otherwise it continues normally\&. GMP\-ECM is stopped while \fIcmd\fR runs, offering a way for letting GMP\-ECM sleep for example while the system is otherwise busy\&. .SH "MISCELLANEOUS" .TP \fB\-n\fR Run the program in ``nice'' mode (below normal priority)\&. .TP \fB\-nn\fR Run the program in ``very nice'' mode (idle priority)\&. .TP \fB\-B2scale \fIf\fR\fR Multiply the default step 2 bound \fIB2\fR by the floating\-point value \fIf\fR\&. Example: \fB\-B2scale 0\&.5\fR divides the default \fIB2\fR by 2\&. .TP \fB\-stage1time \fIn\fR\fR Add \fIn\fR seconds to stage 1 time\&. This is useful to get correct expected time with \fI\-v\fR if part of stage 1 was done in another run\&. .TP \fB\-cofdec\fR Force cofactor output in decimal (even if expressions are used)\&. .TP \fB\-h\fR, \fB\-\-help\fR Display a short description of ecm usage, parameters and command line options\&. .SH "INPUT SYNTAX" .PP The input numbers can have several forms: .PP Raw decimal numbers like 123456789\&. .PP Comments can be placed in the file: everything after ``//'' is ignored, up to the end of line\&. .PP Line continuation\&. If a line ends with a backslash character ``\\'', it is considered to continue on the next line\&. .PP Common arithmetic expressions can be used\&. Example: \fI3*5+2^10\fR\&. .PP Factorial: example \fI53!\fR\&. .PP Multi\-factorial: example \fI15!3\fR means 15*12*9*6*3\&. .PP Primorial: example \fI11#\fR means 2*3*5*7*11\&. .PP Reduced primorial: example \fI17#5\fR means 5*7*11*13*17\&. .PP Functions: currently, the only available function is \fIPhi(x,n)\fR\&. .SH "EXIT STATUS" .PP 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: .TP Bit 0 0 if normal program termination, 1 if error occured .TP Bit 1 0 if no proper factor was found, 1 otherwise .TP Bit 2 0 if factor is composite, 1 if factor is a probable prime .TP Bit 3 0 if cofactor is composite, 1 if cofactor is a probable prime .PP Thus, the following exit status values may occur: .TP 0 Normal program termination, no factor found .TP 1 Error .TP 2 Composite factor found, cofactor is composite .TP 6 Probable prime factor found, cofactor is composite .TP 8 Input number found .TP 10 Composite factor found, cofactor is a probable prime .TP 14 Probable prime factor found, cofactor is a probable prime .SH "BUGS" .PP Report bugs to , after checking for bug fixes or new versions\&. .SH "AUTHORS" .PP Pierrick Gaudry contributed efficient assembly code for combined mul/redc; .PP Jim Fougeron contributed the expression parser and several command\-line options; .PP Laurent Fousse contributed the middle product code, the autoconf/automake tools, and is the maintainer of the Debian package; .PP Alexander Kruppa contributed the Toom\-Cook multiplication code, the special code for Fermat numbers, and many other nice things; .PP Dave Newman contributed the Kronecker\-Schoenhage multiplication code; .PP Paul Zimmermann is the author of the first version of the program\&. .PP Note: email addresses have been obscured, the required substitutions should be obvious\&.