Reynald Lercier

A. Joux et R. Lercier. The Function Field Sieve is quite special. Dans C. Fieker et D.R. Kohel, editeurs, Algorithmic Number Theory: 5th International Symposium, ANTS-V, Sydney, Australia, July 7-12, 2002. Proceedings, volume 2369 de Lecture Notes in Computer Science, pages 431-445. Springer Berlin / Heidelberg, Juillet 2002.

Dans cet article, nous décrivons des améliorations à l'algorithme “Function Field Sieve” (FFS) utilisé pour le calcul de logarithmes discrets dans GF(pⁿ) quand p est petit. Notre contribution principale est une nouvelle façon de construire les corps de fonctions nécessaires à l'algorithme. Avec cette nouvelle construction, la complexité heuristique est aussi bonne que la complexité de celle proposée par Adleman et Huang en 1999, i.e L_p^n[1/3,c] = exp((c+o(1))log(pⁿ)⁽1/3)log (log (pⁿ))⁽2/3)) où c = (32/9)⁽1/3). Avec ces deux constructions, FFS devient un équivalent du crible algébrique spécial utilisé pour factoriser des entiers de la forme A^N +/- B. D'un point de vue asymptotique, c'est plus rapide que des algorithmes plus anciens commme celui de Coppersmith ou la version initiale de FFS d'Adleman. D'un point de vue pratique, nous mettons en avant que cette construction a de meilleures propriétés que la construction d'Adleman et Huang. Nous démontrons l'efficacité de l'algorithme en calculant avec succès des logarithmes discrets dans un grand corps fini de caractéristique 2, i.e GF(2⁵²¹).

[ bib | preprint | publication ] Retour