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. **** 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

-dlp -ell