Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


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

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

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

       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.

	   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 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

	   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.

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

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

       -t n
	   Perform trial division up to	n, before P-1, P+1 or ECM. In loop
	   mode	(see option -c), trial division	is only	performed in the first

       -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

       -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

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

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

	   Verbose mode. More information is printed, more -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

	   Print a time	stamp whenever a new ECM curve or P+1 or P-1 run is

       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.

	   Use GMP's mpz_mod function (sub-quadratic for large inputs, but
	   induces some	overhead for small ones).

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

	   Use Montgomery's multiplication (sub-quadratic version).
	   Theoretically optimal for large input.

	   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.

       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

       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.

	   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.

	   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.

	   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.

       -ve n
	   In loop mode, in the	second and following runs, output only
	   expressions that have at most n characters. Default is -ve 0.

       -i n
	   In loop mode, increment B1 by n after each curve.

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

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

       -prpcmd cmd
	   Execute command 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
	   Executes command 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"
' 11e6 <

       -idlecmd	cmd
	   Executes command 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.

	   Run the program in "nice" mode (below normal	priority).

	   Run the program in "very nice" mode (idle priority).

       -B2scale	f
	   Multiply the	default	step 2 bound B2	by the floating-point value f.
	   Example: -B2scale 0.5 divides the default B2	by 2.

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

	   Force cofactor output in decimal (even if expressions are used).

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

	   Prints configuration	parameters used	for the	compilation and	exits.

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

       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 occured

       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:

	   Normal program termination, no factor found


	   Composite factor found, cofactor is composite

	   Probable prime factor found,	cofactor is composite

	   Input number	found

	   Composite factor found, cofactor is a probable prime

	   Probable prime factor found,	cofactor is a probable prime

       Report bugs to <>, after checking
       <> for bug fixes or
       new versions.

       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)>	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)> 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/17/2010				ECM(1)


Want to link to this manual page? Use this URL:

home | help