The number field sieve in the medium prime case

Antoine Joux, Reynauld Lercier, Nigel Smart, Fre Vercauteren

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

67 Citations (Scopus)


In this paper, we study several variations of the number field sieve to compute discrete logarithms in finite fields of the form $\GF{p^n}$, with $p$ a medium to large prime. We show that when $n$ is not too large, this yields a $L_{p^n}(1/3)$ algorithm with efficiency similar to that of the regular number field sieve over prime fields. This approach complements the recent results of Joux and Lercier on the function field sieve. Combining both results, we deduce that computing discrete logarithms have heuristic complexity $L_{p^n}(1/3)$ in all finite fields. To illustrate the efficiency of our algorithm, we computed discrete logarithms in a 120-digit finite field $\F_{p^3}$.
Translated title of the contributionThe number field sieve in the medium prime case
Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2006
PublisherSpringer Berlin Heidelberg
Pages326 - 344
Number of pages19
Publication statusPublished - 2006

Bibliographical note

ISBN: 9783540374329
Publisher: Springer
Name and Venue of Conference: Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, August 20-24
Conference Organiser: IACR


Dive into the research topics of 'The number field sieve in the medium prime case'. Together they form a unique fingerprint.

Cite this