Reynald Lercier

A. Joux et R. Lercier. Counting points on elliptic curves in medium characteristic. Cryptology ePrint Archive, Report 2006/176, Mai 2006.

Dans cet article, nos revisitons le problème du calcul du noyau d'une isogénie séparable de degré l entre deux courbes elliptiques définies sur un corps finis GF(q) de caractéristique p. Nous décrivons un algorithme de complexité asymptotique proche de O(l²(1+l / p)logq) opérations élémentaires. Cet algorithme est particulièrement utile quand l > p et comme sous-produit, nous obtenons une amélioration de l'algorithme de comptage de point SEA pour de petites valeurs de p. Plus précisément, nous obtenons une complexité heuristique proche de O(log⁴ q) et une complexité en espace égale à O(log² q), dans le cas jusqu'à présent défavorable où p est proche de logq. Comparée aux meilleurs algorithmes aujourd'hui connus pour compter des points, les nécessités mémoire de notre variante de SEA sont plus petites d'un facteur log² q.

[ bib | preprint | publication ] Retour