The Number Field Sieve in the Medium Prime Case - Université Pierre et Marie Curie Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

The Number Field Sieve in the Medium Prime Case

Antoine Joux
Nigel Smart
  • Fonction : Auteur
  • PersonId : 867217

Résumé

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

Dates et versions

hal-01102034 , version 1 (12-01-2015)

Identifiants

Citer

Antoine Joux, Reynald Lercier, Nigel Smart, Frederik Vercauteren. The Number Field Sieve in the Medium Prime Case. CRYPTO 2006, Aug 2006, Santa Barbara, United States. ⟨10.1007/11818175_19⟩. ⟨hal-01102034⟩
198 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More