-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathREADME.dlp
142 lines (110 loc) · 6.43 KB
/
README.dlp
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
Using CADO-NFS for DLP in large characteristic fields.
------------------------------------------------------
**** Basic usage: DLP in GF(p)
The cado-nfs.py script can be used to compute discrete logarithms in a
prime field GF(p). For example, to compute the discrete logarithm in GF(p)
modulo the factor 101538509534246169632617439 of p-1 of the target
92800609832959449330691138186 with p=191907783019725260605646959711:
$ ./cado-nfs.py -dlp -ell 101538509534246169632617439 target=92800609832959449330691138186 191907783019725260605646959711
In principle, just typing
./cado-nfs.py -dlp -ell <ell> target=<target> <p>
should compute the discrete logarithm of <target> modulo <ell> in
GF(<p>). Right now, there are parameters only for primes p of around 30,
60, 100 or 155 digits (to be checked in parameters/dlp subdirectory). If no
target is given, then the output is a file containing the virtual
logarithms of all the factor base elements.
More flexibility is possible. An example of parameter file is given in
parameters/dlp/param.p60. Compared to parameter files for integer
factorization, the main difference is that the lines related
to characters and sqrt disappear and that there is an additional block of
parameters related to individual logarithms.
After the computation is finished, it is possible to run again the
cado-nfs.py script, with a different target: only the last step will be
run. For ensuring that the precomputed data is really used, copy-paste
the command-line indicated in the output of the first computation that
contains "If you want to compute a new target…", and set the new target at the
end.
Important note: the logarithms are given in an arbitrary (unknown) base.
If you want to define them with respect to a specific generator g, then
you'll have to compute the logarithm of g and then divide all the logs by
this value. See https://sympa.inria.fr/sympa/arc/cado-nfs/2018-11/msg00001.html
and
https://sympa.inria.fr/sympa/arc/cado-nfs/2018-11/msg00003.html .
**** Using Joux-Lercier polynomial selection
By default, the same polynomial selection algorithm as for factoring is
used. In some (many ?) cases, it can be much better to use Joux-Lercier's
polynomial selection as implemented in polyselect/dlpolyselect. In order
to use it, it is necessary to add the parameter
jlpoly = true
and to give the additional parameters:
tasks.polyselect.degree = 3
tasks.polyselect.bound = 5
tasks.polyselect.modm = 5
Here, polynomial.degree is the degree of the polynomial with small
coefficients. The other one will have degree one less. Therefore, on this
example, this is a selection for degrees (3,2). The polynomial.bound
and the polynomial.modm parameters are passed directly to dlpolyselect.
The search is parallelized with the client/server mechanism as for the
classical polynomial selection. Each task does one value "modr" between 0
and modm-1 (again, this is dlpolyselect terminology). The number of tried
polynomials is roughly (2*bound+1)^(degree+1), thus here 14641 (the larger
the better, but then polynomial selection will last longer).
For instance, the 30-digit example above can be done with JL polynomial
selection with the following command-line:
$ ./cado-nfs.py -dlp -ell 101538509534246169632617439 191907783019725260605646959711 jlpoly=true tasks.polyselect.bound=5 tasks.polyselect.modm=7 tasks.polyselect.degree=3 tasks.reconstructlog.checkdlp=false
In that case, the individual logarithm phase implementation is based on
GMP-ECM, so this is available only if this library is installed and
detected by the configuration script (see local.sh.example for indicating
non-standard locations).
Note that tasks.reconstructlog.checkdlp=false is there to disable some
consistency checks that can not be made in JL mode.
This is still experimental, but parameters optimized for the JL
polynomial selection can be found in parameters/dlp/Joux-Lercier/ .
Copying
parameters/dlp/Joux-Lercier/params.p30
to
parameters/dlp/params.p30
will automatically activate the JL polynomial selection (but will crash
if GMP-ECM failed to be detected at compile time) for primes of this
size. For instance,
$ ./cado-nfs.py -dlp -ell 101538509534246169632617439 target=92800609832959449330691138186 191907783019725260605646959711
should then work and compute the log of the given target using JL.
**** Using non-linear polynomials
Just like for factorization, it is possible to use two non-linear
polynomials for DLP. Apart from Joux-Lercier polynomial selection (see above),
the user must provide the polynomial file. Also, the current descent script
will not work.
See README.nonlinear for an example of importing a polynomial file with 2
non-linear polynomials.
An important issue is that since the descent is not yet functional
for this case, the script has no way to check the results if there is no
linear polynomial. A good idea is to set
tasks.reconstructlog.partial = false
so that many consistency checks are performed while using all the
relations that were deleted during the filter.
**** Discrete logarithms in GF(p^k) for small k
The algorithm works "mutatis mutandis" for discrete logarithm computations
in GF(p^k). The only difference is that the two polynomials must have a
common irreducible factor of degree k over GF(p). Polynomial selection
for this case is not yet included, so you must build them by yourself,
based on constructions available in the literature, and import it as
indicated in scripts/cadofactor/README. Also the individual
logarithm has to be implemented for that case.
For DLP in GF(p^2), things are sligthly more integrated:
./cado-nfs.py <p> -dlp -ell <ell> -gfpext 2
should work for p = 7 mod 8, provided that a parameter file is available
for the size of p (at the time of writing this doc, only p of 20 decimal
digits is supported).
**** Creating your own parameter files
If the parameter file for your target size is missing, you can create them
by interpolating/extrapolating between existing parameter files. You need both
params.pNNN and pNNN.hint where NNN is your target size. For the hint file, see
parameters/dlp/README.
**** Known issues
Linear algebra for DLP is presently only for x86_64.
The code requires that the modulus width be explicitly covered in the compile
time settings. For example put in local.sh:
BWC_GFP_ARITHMETIC_BACKENDS=p4
(or a list like BWC_GFP_ARITHMETIC_BACKENDS="p1;p4;pz"), where p4 means a
modulus of 4 words, and pz means a modulus of an arbitrary number of words
(slower). Widths up to 15 words are compiled by default.