Skip to content

The number field sieve in the medium prime case

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2006
Publisher or commissioning bodySpringer Berlin Heidelberg
Pages326 - 344
Number of pages19
Volume4117
DOIs
DatePublished - 2006

Abstract

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}$.

Additional information

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

View research connections

Related faculties, schools or groups