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