On Elkies subgroups of l-torsion points in elliptic curves defined over a finite field

2008/09/16 by Reynald Lercier, Lercier, Reynald, Thomas Sirvent +1
Mathematics · #11T71 #11T99 #14G50 #14H52 #FOS: Mathematics #Number Theory (math.NT) #math.NT #msc:11T71 #msc:11T99 #msc:14G50 #msc:14H52

paper · pdf · doi:10.48550/arxiv.0809.2774

13 pages

arxiv created 2008/09/16 · arxiv updated 2009/12/01

Abstract

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, log q)²) 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 for the first time an algorithm valid without any limitation on l and p but of similar complexity.

Related

• Counting points on abelian surfaces over finite fields with Elkies's method
• The Counting function for Elkies primes
• Pursuing polynomial bounds on torsion
• Computing the cardinality of CM elliptic curves using torsion points
• Bounding the torsion in CM elliptic curves