should compute the discrete logarithm of

). Right now, there are parameters only for primes p of around 30, -60, 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. +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. The main difference is that the lines related +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. @@ -34,16 +31,68 @@ 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. -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. +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. + **** 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. Also, the -current descent script will not work. +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. @@ -61,7 +110,8 @@ 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. Also the individual +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: