Reynald Lercier

A. Joux et R. Lercier. “Chinese & Match”, an alternative to Atkin's “Match and Sort” method used in the SEA algorithm. Mathematics of Computation, 70(234):827-836, Avril 2001.

La méthode classique pour déterminer le nombre de points de courbes elliptiques définies sur des corps finis à partir de données partielles obtenues avec l'algorithme SEA (Schoof, Elkies, Atkin) est la méthode “Match and Sort” due à Atkin. Cette méthode est une façon de trouver via un algorithme de type “pas de bébés, pas de géants” le nombre de points parmi C candidats à l'aide de O(sqrt(C)) additions sur courbes elliptiques. La méthode décrite dans cet article se débarrasse des additions sur courbes elliptiques en se servant du fait que l'on a souvent bien plus d'information au sujet du nombre de points que ce qui est réellement utilisé par la méthode d'Atkin. Cela conduit à un algorithme de complexité similaire mais l'espace nécessaire est moindre que celui nécessaire par la méthode d'Atkin. En pratique, cette méthode est bien plus efficace que celle d'Atkin puisqu'elle nous a permis de mener à bien le calcul du nombre de points d'une courbe elliptique définie sur GF(2¹⁶⁶³), ce qui, autant que nous le sachions, est le plus important calcul de ce type jamais réalisé. Un avantage supplémentaire est qu'il est immédiat de paralléliser ce calcul sur un réseau d'ordinateurs.

[ bib | preprint | publication ] Retour