Computing Individual Discrete Logarithms Faster in GF(p^n)

Aurore Guillevic (1, 2)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption

The Number Field Sieve (NFS) algorithm is the best known method to compute discrete logarithms (DL) in large characteristic finite fields Fp^n , with p large and n ≥ 1 small. This algorithm comprises four steps: polynomial selection, relation collection, linear algebra and finally, individual logarithm computation. The first step outputs two numbers fields equipped with a map to Fp^n. After the relation collection and linear algebra phases, the (virtual) logarithm of a subset of elements in each number field is known. The fourth step computes a preimage in one number field of the target element in Fp^n. If one can write the target preimage as a product of elements of known (virtual) logarithm, then one can deduce the discrete logarithm of the target. The traditional approach for the individual logarithm step can be extremely slow, and it is too slow especially for n greater than 3. Its asymptotic complexity is L_Q [1/3, c] with c ≥ 1.44. We present a new preimage computation that provides a dramatic improvement for individual logarithm computations for small n, both in practice and in asymptotic running-time: we have L_Q [1/3, c] with c = 1.14 for n = 2, 4, c = 1.26 for n = 3, 6 and c = 1.34 for n = 5. Our method generalizes to any n; in particular c < 1.44 for the two state-of-the-art variants of NFS for extension fields.

Mots clés: discrete logarithm; finite field; number field sieve; individual logarithm; NFS

Domaines: Cryptographie et sécurité [cs.CR]

Aurore Guillevic. Computing Individual Discrete Logarithms Faster in GF(p^n). 2015. ⟨hal-01157378v1⟩