The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields
Résumé
In this paper, we study the discrete logarithm problem in medium and high characteristic finite fields. We propose a variant of the Number Field Sieve~(NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\mathbb{F}_{p^n}$ for the whole range of applicability of NFS and lowers the asymptotic complexity from $L_{p^n}(1/3,(128/9)^{1/3})$ to $L_{p^n}(1/3,(2^{13}/3^6)^{1/3})$ in the medium characteristic case, and from $L_{p^n}(1/3,(64/9)^{1/3})$ to $L_{p^n}(1/3,((92 + 26 \sqrt{13})/27))^{1/3})$ in the high characteristic case.
Version 2 contains an erratum.
Dans cet article, nous étudions le problème du logarithme discret dans les corps finis de moyenne et grande caractéristique. Nous proposons une variante du crible algébrique basée sur plusieurs corps de nombres. Nous obtenons une accélération de $L_{p^n}(1/3,(128/9)^{1/3})$ à $L_{p^n}(1/3,(2^{13}/3^6)^{1/3})$ pour la moyenne caractéristique et de $L_{p^n}(1/3,(64/9)^{1/3})$ à $L_{p^n}(1/3,((92 + 26 \sqrt{13})/27))^{1/3})$ pour la grande. La version 2 contient un erratum.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...