Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
The Number Field Sieve in the Medium Prime Case
verfasst von : Antoine Joux, Reynald Lercier, Nigel Smart, Frederik Vercauteren
Erschienen in: Advances in Cryptology - CRYPTO 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we study several variations of the number field sieve to compute discrete logarithms in finite fields of the form
${\mathbb F}_{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
${\mathbb F}_{p^3}$
.