Cryptology ePrint Archive: Report 2015/513

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

Aurore Guillevic

Abstract: The Number Field Sieve (NFS) algorithm is the best known method to compute discrete logarithms (DL) in large characteristic finite fields $\FF_{p^n}$, with $p$ large and $n \geq 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 $\FF_{p^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 $\FF_{p^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 \geq 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.

Category / Keywords: public-key cryptography / discrete logarithm, finite field, number field sieve, NFS, individual logarithm

Date: received 27 May 2015, last revised 27 May 2015

Contact author: guillevic at lix polytechnique fr

Available format(s): PDF | BibTeX Citation

Version: 20150529:075412 (All versions of this report)

Short URL: ia.cr/2015/513

Discussion forum: Show discussion | Start new discussion