Reynald Lercier

R. Lercier et T. Sirvent. On elkies subgroups of l-torsion points in elliptic curves defined over a finite field. Journal de Théorie des Nombres de Bordeaux, 20(3):783-797, Décembre 2008.

En sous-résultat de l'algorithme de Schoof-Elkies-Atkin pour compter le nombre de points d'une courbe elliptique définie sur un corps fini de caractéristique p, il existe un algorithme qui, pour l un nombre premier d'Elkies, calcule des points de l-torsion dans une extension de degré l-1 à l'aide de O˜(l max(l, logq)²) opérations élémentaires à condition que l<=p/2. Nous combinons ici un algorithme rapide dû à Bostan, Morain, Salvy et Schost avec l'approche p-adique suivie par Joux et Lercier pour obtenir un algorithme valide sans limitation sur l et p et de complexité similaire. Par soucis de simplification, nous décrivons précisément ici l'algorithme dans le cas des corps finis de caractéristique p>=5. Nous l'illustrons aussi avec quelques expérimentations.

[ bib | preprint | publication ] Retour