Reynald Lercier

R. Lercier. Computing isogenies in GF(2ⁿ). Dans H. Cohen, editeur, Algorithmic Number Theory: Second International Symposium, ANTS-II Talence, France, May 18-23, 1996 Proceedings, volume 1122 de Lecture Notes in Computer Science, pages 197-212. Springer Berlin / Heidelberg, Mai 1996.

Contrairement à ce qui se passe dans les corps finis premiers de grande caractéristique, le coût majeur lorsque l'on compte le nombre de points d'une courbe elliptique E définie sur GF(2ⁿ) est le calcul d'isogénies de degré premier l. La meilleure méthode connue jusqu'à présent est due à Couveignes et nécessite asymptotiquement O(l³) opérations dans le corps. Nous soulignons dans cet article quelques propriétés remarquables satisfaites par ces isogénies et montrons comment on peut obtenir d'elles un nouvel algorithme qui semble meilleur en pratique que celui de Couveignes avec la même complexité. Sur un problème représentatif, on gagne un facteur 5 sur le calcul total.

[ bib | preprint | publication ] Retour