1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

This is the README file for the ecm library.
To use the library, you need to add the following line in your source file:
#include "ecm.h"
and link with lecm.
The public interface is defined in the "ecm.h" file. It contains the following
functions:
int ecm_factor (mpz_t f, mpz_t n, double B1, ecm_params p)
where n is the number to factor, f is the factor found (if any),
B1 is the stage 1 bound, and p contains auxiliary parameters (see below).
When p is NULL, default values for those parameters are chosen.
The ecm_factor() function returns:
* a positive value if a factor was found (1 for step 1, 2 for step 2),
* zero when no factor was found,
* a negative value when an error occurred.
void ecm_init (ecm_params p)
Initialize the parameters to default values.
void ecm_clear (ecm_params p)
Clear the parameters.
Detailed description of parameters (ecm_params):
* p>method is the factorization method (ECM_ECM for ECM, ECM_PM1 for P1,
ECM_PP1 for P+1). Default is ECM_ECM.
* p>x (if non zero) is the starting point (ECM, P1, P+1). For ECM, we take
as starting point (x0 : y0) where x0=x, y0=1; for P1, we take x0;
for P+1, we take x0 as starting point of the Lucas sequence.
When ecm_factor() returns, p>x is the point obtained after stage 1.
* p>param (ECM only) is the parametrization that are going to be used to
compute the curve b*y^2 = x^3 + a*x^2 + x.
ECM_PARAM_DEFAULT let the choice of the parametrization to the program
ECM_PARAM_SUYAMA use Suyama parametrization a = (vu)^3*(3*u+v)/(4*u^3*v)2,
u = s^25, v = 4*s.
The initial point (if p>x is zero) is taken as x0=u^3/v^3, y0=1
(thus b is taken as x0^3 + a*x0^2 + x0).
ECM_PARAM_BATCH_SQUARE (only for 64bit machine) a=4*i^22, x0=2, i is a
random 32bit integer.
ECM_PARAM_BATCH_2 a = 4*d(k)2, x0=2. Use an elliptic parametrization to
compute d(k) such that the curve has a 6torsion point.
ECM_PARAM_BATCH_32BITS_D is mostly use for the gpu computation, a = 4*d2,
x0=2, d is a random 32bit integer.
ECMPARAM_BATCH_SQUARE, ECMPARAM_BATCH_2, ECMPARAM_BATCH_32BITS_D are said
to used batch mode for the scalar multiplication. They should always have
x0 =2
* p>sigma (ECM only) is the value of the parameter used with the
parametrization (choosen with p>param).
ECM_PARAM_SUYAMA p>sigma is s.
ECM_PARAM_BATCH_SQUARE p>sigma is i (32bit integer)
ECM_PARAM_BATCH_2 p>sigma is k, the parameter in the elliptic
parametrization (can be 64bit integer on 64bit machine)
ECM_PARAM_BATCH_32BITS_D p>sigma is d (32bit integer)
* p>sigma_is_A (ECM only) indicates that p>sigma is the 'a' parameter
from the elliptic curve.
* p>go is the initial group order to preload (default is 1).
* p>B1done tells that step 1 was already done up to B1done. This means that
all prime powers <= B1done were dealt with. If for example B1done=100
and B1=200, prime 2 was dealt with up to power 6, thus it remains to
"multiply" once by 2 to go up to power 7. Of course, all primes p such
that B1done < p <= B1 will be considered with power 1.
* p>B2min is the lower bound for stage 2, which will treat all primes p such
that B2min <= p <= B2. If negative, B2min will be set to B1.
* p>B2 is the upper bound for stage 2 (default is automatically computed from
B1, to optimize the efficiency of the method).
* p>k is the number of blocks used in stage 2 (default is ECM_DEFAULT_K).
* p>S defines the polynomial used for BrentSuyama's extension in stage 2.
If positive, the polynomial used is x^S; if negative, it is Dickson's
polynomial of degree S with parameter a=1, where D_{1,a}(x) = x,
D_{2,a}(x) = x^22*a, and D_{k+2,a}(x) = x*D_{k+1,a}(x)  a*D_{k,a}(x),
or equivalently D_{k,a}(2*sqrt(a)*cos(t)) = 2*a^(k/2)*cos(k*t).
If zero, choice is automatic (and should be close to optimal).
Default is ECM_DEFAULT_S.
* p>repr defines the representation used for modular arithmetic: 1 means
the 'mpz' class from GMP, 2 means 'modmuln' (Montgomery's multiplication,
quadratic implementation), 3 means 'redc' (Montgomery's multiplication,
subquadratic implementation), 1 indicates not to use a special base2
representation (when the input number is a factor of 2^n +/ 1).
Other values (including 0) mean the representation will be chosen
automatically (hopefully in some optimal way).
* p>nobase2step2 disable special base2 code in ecm stage 2 only
* p>verbose is the verbosity level: 0 for no output, 1 for normal output
(like default for GMPECM), 2 for diagnostic output without inter
mediate residues (like v in GMPECM), 3 for diagnostic output with
residues (like v v), 4 for high diagnostic output (v v v),
and 5 for trace output (v v v v).
* p>os is the output stream used for verbose output. Default is stdout.
* p>es is the output stream used for errors. Default is stderr.
* p>TreeFilename if non NULL, is the file name to store the product tree
of F (option treefile f).
* p>maxmem is the maximum amount of memory in bytes that should be used in
stage 2. Setting this value too low (< 10MB, say) will cause stage 2
to perform very poorly, or return with an error code.
* p>stage1time is the time already spent in stage 1 (useful to get a correct
estimation of the expected time to find factors).
* p>rng is a random number generator state.
* p>use_ntt if equal to 1, use NTT in stage 2.
* p>(*stop_asap) pointer to function: if the function returns zero, continue
normally, otherwise exit as soon as possible. May be NULL.
* batch_s, batch_last_B1_used,
* p>gpu, p> gpu_device, p>gpu_device_init, p>gpu_number_of_curves
See README.gpu
