File: README.lib

package info (click to toggle)
gmp-ecm 7.0.4+ds-5
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 4,728 kB
  • sloc: asm: 36,431; ansic: 34,057; xml: 885; python: 799; sh: 698; makefile: 348
file content (113 lines) | stat: -rw-r--r-- 5,801 bytes parent folder | download | duplicates (2)
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 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