FreeBSD Manual Pages

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
alternatively one may use the 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
Perform P-1 instead of the default method (ECM).

-pp1
Perform P+1 instead of the default method (ECM).

GROUP AND INITIAL POINT	PARAMETERS
-x0 x
[ECM, P-1, P+1] Use 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
[ECM] Use s (arbitrary-precision integer) as	curve generator. If
omitted, s is generated at random.

-A a
[ECM] Use a (arbitrary-precision integer) as	curve parameter. If
omitted, is it generated from the sigma value.

-go val
[ECM, P-1, P+1] Multiply the	initial	point by 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
[ECM, P-1, P+1] Perform 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
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 file.1, file.2 etc.	Does not work with fast	stage
2 for P+1 and P-1.

-power n
[ECM, P-1] Use x^n for Brent-Suyama's extension (-power 1 disables
Brent-Suyama's extension). The default polynomial is	chosen
depending on	the method and B2. For P-1 and P+1, disables the fast
stage 2. For	P-1, n must be even.

-dickson	n
[ECM, P-1] Use degree-n Dickson's polynomial	for Brent-Suyama's
extension. For P-1 and P+1, disables	the fast stage 2. Like for
-power, n must be even for P-1.

-maxmem n
Use at most n megabytes of memory in	stage 2.

-ntt, -no-ntt
Enable or disable the Number-Theoretic Transform code for
polynomial arithmetic in stage 2. With NTT, dF is chosen to be a
power of 2, and is limited by the number suitable primes that fit
in a	machine	word (which is a limitation only on 32 bit systems).
The -no-ntt variant uses more memory, but is	faster than NTT	with
large input numbers.	By default, NTT	is used	for P-1, P+1 and for
ECM on numbers of size at most 30 machine words.

OUTPUT
-q
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).

-v
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
Print a time	stamp whenever a new ECM curve or P+1 or P-1 run is
processed.

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
Use GMP's mpz_mod function (sub-quadratic for large inputs, but
induces some	overhead for small ones).

-modmuln
Use Montgomery's multiplication (quadratic version).	Usually	best
method for small input.

-redc
Theoretically optimal for large input.

-nobase2
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 -v).

-base2 n
Force use of	special	base-2 code, input number must divide 2^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
Take	input from file	file instead of	from standard input.

-save file
Save	result of step 1 in 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
Like	-save, but appends to existing files.

-resume file
Resume residues from	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
Periodically	write the current residue in stage 1 to	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
Perform 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
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.

-b
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 -inp.

-d
Depth-first processing: in loop mode, run n curves for the first
number, then	n curves for the second	one and	so on. This is the
default mode	with standard input.

-I n
In loop mode, multiply 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 options allow for executing shell commands	to supplement
functionality to	GMP-ECM.

MISCELLANEOUS
-stage1time n
Add 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.

-h, --help
Display a short description of ecm usage, parameters	and command
line	options.

-printconfig
Prints configuration	parameters used	for the	compilation and	exits.

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^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: currently, the only available	function is Phi(x,n).

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
0 if	normal program termination, 1 if error occurred

Bit 1
0 if	no proper factor was found, 1 otherwise

Bit 2
0 if	factor is composite, 1 if factor is a probable prime

Bit 3
0 if	cofactor is composite, 1 if cofactor is	a probable prime

Thus, the following exit	status values may occur:

0
Normal program termination, no factor found

1
Error

2
Composite factor found, cofactor is composite

6
Probable prime factor found,	cofactor is composite

8
Input number	found

10
Composite factor found, cofactor is a probable prime

14
Probable prime factor found,	cofactor is a probable prime

BUGS
Report bugs to <ecm-discuss@lists.gforge.inria.fr>, after checking
<http://www.loria.fr/~zimmerma/records/ecmnet.html> for bug fixes or
new versions.

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.

April 22, 2003			  03/01/2013				ECM(1)

NAME | SYNOPSIS | DESCRIPTION | STEP 1 AND STEP 2 BOUND PARAMETERS | FACTORING METHOD | GROUP AND INITIAL POINT PARAMETERS | STEP 2 PARAMETERS | OUTPUT | MODULAR ARITHMETIC OPTIONS | FILE I/O | LOOP MODE | SHELL COMMAND EXECUTION | MISCELLANEOUS | INPUT SYNTAX | EXIT STATUS | BUGS | AUTHORS

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=ecm&sektion=1&manpath=FreeBSD+13.0-RELEASE+and+Ports>