Using CADO-NFS for DLP in large characteristic fields. ------------------------------------------------------ **** Basic usage: DLP in GF(p) The script and the wrapper can be used to compute discrete logarithms in a prime field GF(p). For the moment, it is required to have Magma installed. It is used just for some number-theoretic computations, after the polynomial selection has been done. Cf scripts/badideals.mag . This script has been written without using any high-level functionality of Magma, so that it will be easy to convert it to C/C++/Python. This step is very cheap, so it is possible to run it on any computer. In principle, just typing ./

-dlp -ell target= should compute the discrete logarithm of modulo in GF(

). Right now, there are parameters only for primes p of around 30 or 60 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. A direct use of 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. The other example params_dl/param.p30, shows how to give parameters for the descent. 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 gorder=... in the parameter file. Note that this automatic factoring feature might disappear in the future: you'd better consider already that the parameter gorder is mandatory (furthermore, its name is likely to change to ell). 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. 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 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. Also the individual logarithm has to be implemented for that case. For DLP in GF(p^2), things are sligthly more integrated: ./

-dlp -ell -gfpext 2 should work for p mod 8 = 7, 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).