Discrete Logarithms

Let K be a field of cardinality q=p^k, with p prime. Magma contains several advanced algorithms for computing discrete logarithms of elements of K. The two main kinds of algorithms used are as follows: (1) Pohlig-Hellman [PH78]: The running time is usually proportional to the square root of the largest prime l dividing q - 1; this is combined with the Shanks baby-step/giant-step algorithm (when l is very small) or the Pollard-ρ algorithm. (2) Index-Calculus: There is first a precomputation stage which computes and stores all the logarithms of a factor base (all the elements of the field corresponding to irreducible polynomials up to some bound) and then each subsequent individual logarithm is computed by expressing the given element in terms of the factor base.

The different kinds of finite fields in Magma are handled as follows (in this order):

(a)

Small Fields (any characteristic):

If the largest prime l dividing q - 1 is reasonably small (typically, less than 2³⁶), the Pohlig-Hellman algorithm is used (the characteristic p is irrelevant).

(b)

Large Prime :

Suppose K is a prime field (so q=p). Then the Gaussian integer sieve [COS86], [LO91a] is used if p has at least 4 bits but no more than 400 bits, p - 1 is not a square, and one of the following is a quadratic residue modulo p: -1, -2, -3, -7, or -11. If the Gaussian integer sieve cannot be used and if p is no more than 300-bits, then the linear sieve [COS86], [LO91a] is used. The precomputation stage always takes place and typically requires a lot more time than for computing individual logarithms (and may also require a lot of memory for large fields). Thus, the first call to the function Log below may take much more time than for subsequent calls. Also, for large prime fields, in comparison to the Gaussian method the linear sieve requires much more time and memory than the Gaussian method for the precomputation stage, and therefore it is only used when the Gaussian integer algorithm cannot be used. See the example H28E3 in the chapter on sparse matrices for an explanation of the basic linear sieve algorithm and for more information on the sparse linear algebra techniques employed.

(c)

Small Characteristic, Non-prime :

Since V2.19, if K is a finite field of characteristic p, where p is less than 2³⁰, then an implementation by Allan Steel of Coppersmith's index-calculus algorithm [Cop84], [GM93], [Tho01] is used. (Strictly speaking, Coppersmith's algorithm is for the case p=2 only, but a straightforward generalization is used when p>2.) A suite of external auxiliary tables boost the algorithm so that the precomputation stage computation to determine the logarithms of a factor base can be avoided for a large number of fields of very small characteristic. This means that logarithms of individual elements can be computed immediately if a relevant table is present for the specific field. By default, tables are included in the standard Magma distribution at least for all fields of characteristic 2, 3, 5 or 7 with cardinality up to 2²⁰⁰. The user can optionally download a much larger suite of tables from the Magma optional downloads page http://magma.maths.usyd.edu.au/magma/download/db/ (files FldFinLog_2.tar.gz, etc.; about 5GB total).

(d)

Large Characteristic, Non-prime :

In all other cases, the Pohlig-Hellman algorithm is used.

Log(x) : FldFinElt -> RngIntElt

The discrete logarithm of the non-zero element x from the field F, i.e., the unique integer k such that x = w^k and 0 ≤k < (#F - 1), where w is the primitive element of F (as returned by PrimitiveElement). Default parameters are automatically chosen if an index-calculus method is used (use Sieve below to set parameters). See also the procedure SetPrimitiveElement.

Log(b, x) : FldFinElt, FldFinElt -> RngIntElt

The discrete logarithm to the base b of the non-zero element x from the field F, i.e., the unique integer k such that x = b^k and 0 ≤k < (#F - 1). If b is not a primitive element, then in some unusual cases the algorithm may take much longer than normal.

ZechLog(K, n) : FldFin, RngIntElt -> RngIntElt

The Zech logarithm Z(n) of the integer n for the field F, which equals the logarithm to base w of wⁿ + 1, where w is the primitive element of F. If wⁿ is the minus one element of K, then -1 is returned.

Sieve(K) : FldFin ->

    Lanczos: BoolElt                    Default: false

(Procedure.) Call the Gaussian integer sieve on the prime finite field K if possible; otherwise call the linear sieve on K (assuming K is not too small).

If the parameter Lanczos is set to true, then the Lanczos algorithm [LO91b, Sec. 3] will be used for the linear algebra phase. This is generally very much slower than the default method (often 10 to 50 times slower), but it will take considerably less memory, so may be preferable for extremely large fields. See also the function ModularSolution in the chapter on sparse matrices for more information.

SetVerbose("FFLog", v) : MonStgElt, RngIntElt ->

(Procedure.) Set the verbose printing level for the finite field logarithm algorithm to be v. Currently the legal values for v are 0, 1, and 2. If the level is 1, information is printed whenever the logarithm of an element is computed (unless the field is very small, in which case a lookup table is used). The value of 2 will print a very large amount of information.

> F<z> := FiniteField(7^4);
> PrimitiveElement(F);
z;
> Log(z);
1
> Log(z^2);
2
> Log(z + 1);
419
> z^419 eq z + 1;
true
> b := z + 1;
> b;
z^419
> Log(b, b);
1
> Log(b, z);
779
> b^779 eq z;
true

> F<z> := GF(2, 73);
> Factorization(#F-1);
[ <439, 1>, <2298041, 1>, <9361973132609, 1> ]
> PrimitiveElement(F);
z
> time Log(z + 1);
4295700317032218908392
Time: 5.400
> z^4295700317032218908392;
z + 1
> time Log(z + 1);             
4295700317032218908392
Time: 0.000
> time Log(z^2);
2
Time: 0.000
> time Log(z^2134914112412412);
2134914112412412
Time: 0.000
> b := z + 1;
> b;
z + 1
> time Log(b, b);
1
Time: 0.010
> time Log(b, z);
2260630912967574270198
Time: 0.000
> b^2260630912967574270198;
z