Algorithme de comptage de points de Schoof

Mots clés: courbes elliptiques, comptage de points.

Le but de ce projet est d’implanter l’algorithme de comptage de points de courbes elliptiques de Schoof.

Résumé

Déterminer le cardinal d’une courbe elliptique définie sur un corps fini est un problème classique en théorie des nombres. Si est une courbe définie sur un corps fini à éléments, Le théorème de Hasse dit que , avec , où est la trace de l’endomorphisme de Frobenius de .

Le méthodes générales de calcul d’ordre de groupes sont toutes de complexité exponentielle, et ceci à longtemps été le cas aussi pour les courbes elliptiques, pour lesquelles la meilleure méthode connue était l’algorithme de Shanks-Mestre, de complexité . L’utilisation des courbes elliptiques en cryptographie a motivé la recherche d’algorithmes plus efficaces pour ce problème.

Le premier algorithme de comptage de points de complexité polynomiale est dû à Schoof. Il s’agit d’un algorithme multi-modulaire, qui calcule la valeur de la trace modulo plein de petits nombres premiers, et ensuite reconstruit la valeur de par restes chinois. La complexité de l’algorithme de Schoof a été par la suite améliorée par Atkin et Elkies, donnant un algorithme connu aujourd’hui sous le nom SEA.

Le but de ce projet est d’implanter l’algorithme original de Schoof pour des courbes définies sur des corps premiers. Les améliorations d’Atkin et Elkies ne seront pas étudiées ici. Il est conseillé d’utiliser la bibliothèque C de calcul formel Flint pour réaliser le projet.

Prérequis

Objectifs

Références