Computing the eigenvalue in the Schoof-Elkies-Atkin algorithm using Abelian lifts

Preda Mihailescu (1) , François Morain (2, 3) , Eric Schost (4)

1 Mathematisches Institut
2 TANC - Algorithmic number theory for cryptology
3 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
4 ORCCA and Computer Science Department

The Schoof-Elkies-Atkin algorithm is the best known method for counting the number of points of an elliptic curve defined over a finite field of large characteristic. We use abelian properties of division polynomials to design a fast theoretical and practical algorithm for computing the eigenvalue search.

Domaines: Calcul formel [cs.SC]; Théorie des nombres [math.NT]

Preda Mihailescu, François Morain, Eric Schost. Computing the eigenvalue in the Schoof-Elkies-Atkin algorithm using Abelian lifts. 2007. ⟨inria-00130142⟩