A. Joux, R. Lercier, N. Smart, and
F. Vercauteren. The Number Field Sieve in the Medium Prime
Case.
In C. Dwork, editor, Advances in Cryptology -
CRYPTO 2006. 26th Annual International Cryptology Conference, Santa Barbara,
California, USA, August 20-24, 2006, Proceedings, volume 4117 of Lecture
Notes in Computer Science, pages 326-344. Springer Berlin / Heidelberg,
August 2006.
In this paper, we study several variations of the number
field sieve to compute discrete logarithms in finite fields
of the form GF(pn), with p a medium to large
prime. We show that when n is not too large, this yields a
Lp^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 Lp^n(1/3) in all finite fields. To
illustrate the efficiency of our algorithm, we computed
discrete logarithms in a 120-digit finite field
GF(p3).
[ bib |
preprint |
publication ]
Back |
![[fr]](../inc/img/skin/medicis/fr.gif)
![[en]](../inc/img/skin/medicis/en.gif)
