+should compute the discrete logarithm of

). Right now, there are parameters only for primes p of around 30, +60, 100 or 155 digits (to be checked in params_dl/ 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://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2018-November/000939.html and +https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2018-November/000942.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. -A direct use of cadofactor.py allows more flexibility. An example of -parameter file is given in params_dl/param.p59. The main difference is -the presence of the "dlp=true" line, and the lines related to characters -and sqrt disappear. - -By default, the Magma script will factor p-1 and compute discrete logs modulo -the largest prime factor ell of p-1. This can be overridden by giving -explicitly ell=... in the parameter file. - -The process is automatic up to the reconstruction of logarithms from the -output of the linear algebra and the data remembered during the filtering -phase. The result is in the $wordir/$name.reconstruclog.dlog file. - -Individual logarithms, using a descent stage, must be computed by hand -with the help of the sieve/las binary. See sieve/README.descent for some -guidelines. - -Note: the logarithms are given in an arbitrary 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. **** Using non-linear polynomials Just like for factorization, it is possible to use two non-linear -polynomials for DLP. However, the polynomial selection is not automatic -in that case: the user must provide the polynomial file. +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. -The main difference with factorization is that there is no need to add -the nratchars parameters for characters, since the characters binary is -not used in DLP. - -Another important issue is that since the descent is not yet automated, -the script has no way to check the results if there is no linear -polynomial. A good idea is to set +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 +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. - +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

-dlp -ell