International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 29 May 2015

Aurore Guillevic
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.