Fast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm

Pierrick Gaudry (1, 2, 3) , François Morain (1, 3)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 SPACES - Solving problems through algebraic computation and efficient software
3 TANC - Algorithmic number theory for cryptology

The Schoof-Elkies-Atkin algorithm is the only known method for counting the number of points of an elliptic curve defined over a finite field of large characteristic. Several practical and asymptotical improvements for the phase called eigenvalue computation are proposed.

Domaines: Cryptographie et sécurité [cs.CR]

Pierrick Gaudry, François Morain. Fast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm. ISSAC '06: Proceedings of the 2006 international symposium on symbolic and algebraic computation, Jul 2006, Genoa, Italy, pp.109 - 115, ⟨10.1145/1145768.1145791⟩. ⟨inria-00001009⟩