Reynald Lercier

R. Lercier and 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, December 2008.

As a subproduct of the Schoof-Elkies-Atkin algorithm to count points on elliptic curves defined over finite fields of characteristic p, there exists an algorithm that computes, for l an Elkies prime, l-torsion points in an extension of degree l-1 at cost O˜(l max(l, logq)²) bit operations in the favorable case where l<=p/2. We combine in this work a fast algorithm for computing isogenies due to Bostan, Morain, Salvy and Schost with the p-adic approach followed by Joux and Lercier to get an algorithm valid without any limitation on l and p but of similar complexity. For the sake of simplicity, we precisely state here the algorithm in the case of finite fields with characteristic p>=5. We give experiment results too.

[ bib | preprint | publication ] Back