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

DOI10.5802/JTNB.650MaRDI QIDQ1026985zbMATH OpenOpenAlexFDO

Authors Reynald Lercier, Thomas Sirvent

Publication date 30 June 2009

Published in Journal de Théorie des Nombres de Bordeaux (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.2774, http://www.numdam.org/item?id=JTNB_2008__20_3_783_0, https://eudml.org/doc/10860

Mathematics Subject Classification ID

Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16)

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)^2) 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.

Recommendations

• scientific article; zbMATH DE number 1113825
• Counting Points on Elliptic Curves Over F 2 m
• Computing the $\ell $-power torsion of an elliptic curve over a finite field
• scientific article; zbMATH DE number 1210368
• An extension of Satoh's algorithm and its implementation

Cites work

• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 3937328 (Why is no real title available?)
• scientific article; zbMATH DE number 1113825 (Why is no real title available?)
• scientific article; zbMATH DE number 1113839 (Why is no real title available?)
• scientific article; zbMATH DE number 2086697 (Why is no real title available?)
• scientific article; zbMATH DE number 3356934 (Why is no real title available?)
• Algebraic coding theory
• An Analysis of Goubin’s Refined Power Analysis Attack
• Computing modular polynomials in quasi-linear time
• Counting points on elliptic curves over finite fields
• Elliptic periods for finite fields
• Fast algorithms for computing isogenies between elliptic curves
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Galois invariant smoothness basis
• New techniques for the computation of linear recurrence coefficients
• On the coefficients of the transformation polynomials for the elliptic modular function
• On the equivalence between Berlekamp's and Euclid's algorithms (Corresp.)
• Shift-register synthesis and BCH decoding
• The Function Field Sieve in the Medium Prime Case

Cited in

(12)

• Fast computation of elliptic curve isogenies in characteristic two
• On the product of small Elkies primes
• Modular composition modulo triangular sets and applications
• Fast arithmetics in Artin-Schreier towers over finite fields
• Computing isomorphisms and embeddings of finite fields
• Efficient computation of Cantor's division polynomials of hyperelliptic curves over finite fields
• Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic
• Finding the Eigenvalue in Elkies' Algorithm
• Explicit isogenies in quadratic time in any characteristic
• Fast algorithms for computing isogenies between elliptic curves
• Fast computation of hyperelliptic curve isogenies in odd characteristic
• Tracking \(p\)-adic precision

This page was built for publication: On Elkies subgroups of \(\ell\)-torsion points in elliptic curves defined over a finite field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1026985)