`123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113` ``````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 P-1, ECM_PP1 for P+1). Default is ECM_ECM. * p->x (if non zero) is the starting point (ECM, P-1, P+1). For ECM, we take as starting point (x0 : y0) where x0=x, y0=1; for P-1, 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 = (v-u)^3*(3*u+v)/(4*u^3*v)-2, u = s^2-5, 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 64-bit machine) a=4*i^2-2, x0=2, i is a random 32-bit 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 6-torsion point. ECM_PARAM_BATCH_32BITS_D is mostly use for the gpu computation, a = 4*d-2, x0=2, d is a random 32-bit integer. ECM-PARAM_BATCH_SQUARE, ECM-PARAM_BATCH_2, ECM-PARAM_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 (32-bit integer) ECM_PARAM_BATCH_2 p->sigma is k, the parameter in the elliptic parametrization (can be 64-bit integer on 64-bit machine) ECM_PARAM_BATCH_32BITS_D p->sigma is d (32-bit 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 Brent-Suyama'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^2-2*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 base-2 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 base-2 code in ecm stage 2 only * p->verbose is the verbosity level: 0 for no output, 1 for normal output (like default for GMP-ECM), 2 for diagnostic output without inter- mediate residues (like -v in GMP-ECM), 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 ``````