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

DOI10.5802/JTNB.650zbMATH Open1230.11080arXiv0809.2774OpenAlexW2091142228MaRDI QIDQ1026985FDOQ1026985

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)

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.

Full work available at URL: https://arxiv.org/abs/0809.2774

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• 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
• Fast computation of elliptic curve isogenies in characteristic two

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)