Fast algorithms for computing isogenies between elliptic curves

DOI10.1090/S0025-5718-08-02066-8zbMath1200.11097arXivcs/0609020MaRDI QIDQ3577024

Éric Schost, Alin Bostan, François Morain, Bruno Salvy

Publication date: 3 August 2010

Published in: Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

elliptic curves; fast algorithms; finite fields; Newton iteration; isogenies; Schoof-Elkies-Atkin algorithm

Mathematics Subject Classification ID

94A60: Cryptography

11Y16: Number-theoretic algorithms; complexity

11G20: Curves over finite and local fields

Related Items

A Subexponential Algorithm for Evaluating Large Degree Isogenies, Fast computation of elliptic curve isogenies in characteristic two, Computing separable isogenies in quasi-optimal time, On the computation of coefficients of modular forms: The reduction modulo $p$ approach, Computing isogenies between Jacobians of curves of genus 2 and 3, Modular polynomials via isogeny volcanoes, Explicit classification of isogeny graphs of rational elliptic curves, On the distribution of Atkin and Elkies primes, The beta ansatz: a tale of two complex structures, The Diffie-Hellman problem and generalization of Verheul's theorem, Elliptic Gauss sums and applications to point counting, On Elkies subgroups of \(\ell\)-torsion points in elliptic curves defined over a finite field, Cryptographic hash functions from expander graphs, Avoiding side-channel attacks by computing isogenous and isomorphic elliptic curves, Quantum lattice enumeration and tweaking discrete pruning, Distorting the volcano, Towards practical key exchange from ordinary isogeny graphs, Orienting supersingular isogeny graphs, Algebraic approaches for solving isogeny problems of prime power degrees, A taxonomy of pairing-friendly elliptic curves, Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic, Efficient computation of Cantor's division polynomials of hyperelliptic curves over finite fields, Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves, Computational Number Theory and Cryptography, Computing functions on Jacobians and their quotients, Computing cardinalities of -curve reductions over finite fields, Explicit isogenies in quadratic time in any characteristic, Computing the $\ell $-power torsion of an elliptic curve over a finite field, Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies, Cycles in the Supersingular ℓ-Isogeny Graph and Corresponding Endomorphisms, Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography

Uses Software

• NTL

Cites Work

• On fast multiplication of polynomials over arbitrary algebras
• The Hasse invariant and p-division points of an elliptic curve
• Composing power series over a finite ring in essentially linear time
• The middle product algorithm. I: Speeding up the division and square root of power series
• A rational function decomposition algorithm by near-separated polynomials
• Counting points on elliptic curves over finite fields
• Computing the number of points on an elliptic curve over a finite field: algorithmic aspects
• A new polynomial factorization algorithm and its implementation
• On computing reciprocals of power series
• An elliptic curve trapdoor system
• Fast multiplication of large numbers
• An algorithm for division of powerseries
• On the Security of a Practical Identification Scheme
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Fast Algorithms for Manipulating Formal Power Series
• Constructing Isogenies between Elliptic Curves Over Finite Fields
• Subquadratic-time factoring of polynomials over finite fields
• Isomorphisms between Artin-Schreier towers
• Computing isogenies between elliptic curves over $F_{p^n}$ using Couveignes's algorithm
• An Analysis of Goubin’s Refined Power Analysis Attack
• Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item