Reynald Lercier

R. Lercier et D Lubicz. Counting Points on Elliptic Curves over Finite Fields of Small Characteristic in Quasi Quadratic Time. Dans E. Biham, editeur, Advances in Cryptology - EUROCRPYT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003. Proceedings, volume 2656 de Lecture Notes in Computer Science, pages 360-373. Springer Berlin / Heidelberg, Mai 2003.

Soit p, un petit nombre premier et q=pⁿ. Soit E une courbe elliptique définie sur GF(q)). Nous proposons un algorithme qui calcule sans précalculs le j-invariant du relevé canonique de E pour un coût de O(logn) fois le coût nécessaire au calcul du relevé d'une puissance du Frobenius. Soit M défini comme étant une constante telle que le produit de deux entiers de n bits peut être réalisé en O(n^μ) opérations élémentaires, cela conduit à un algorithme pour calculer le nombre de points d'une courbe elliptique qui atteint, au prix d'une complexité en espace de O(n^5/2), une borne théorique de complexité en temps égale à O(n^{max(1.19, μ)+μ+1/2}logn). Quand le corps à une Base Normale Gaussienne de petit type, on obtient de plus un algorithme de complexité en temps égale à O(log(n)n^2μ) et en espace égale à O(n²). D'un point de vue pratique, l'algorithme correspondant est particulièrement bien adapté à une implantation. Nous soulignons cela par un calcul d'une taille de 100002 bits.

[ bib | preprint | publication ] Retour