Reynald Lercier

A. Joux, R. Lercier, N. Smart, et F. Vercauteren. The Number Field Sieve in the Medium Prime Case. Dans C. Dwork, editeur, Advances in Cryptology - CRYPTO 2006. 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, volume 4117 de Lecture Notes in Computer Science, pages 326-344. Springer Berlin / Heidelberg, Août 2006.

Dans cet article, nous étudions plusieurs variantes du crible algébrique pour calculer des logarithmes discrets dans des corps finis de la forme GF(pⁿ), avec p un nombre premier de taille moyenne à grande. Nous exhibons pour n pas trop grand un algorithme de complexité L_p^n(1/3), d'efficacité similaire à celle du crible algébrique classique pour les corps finis premiers. Cette approche complémente les résultats récents de Joux et Lercier sur le crible dans les corps de fonctions. Si l'on combine les deux résultats, on en déduit que calculer des logarithmes discrets atteint une complexité heuristique égale à L_p^n(1/3) dans tous les corps finis. Pour illustrer l'efficacité de notre algorithme, nous calculons des logarithmes discrets dans un corps GF(p³) avec un nombre d'éléments de 120 chiffres.

[ bib | preprint | publication ] Retour