Fast algorithms for computing isogenies between elliptic curves

DOI10.1090/S0025-5718-08-02066-8zbMath1200.11097arXivcs/0609020OpenAlexW2048276889MaRDI 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 curvesfast algorithmsfinite fieldsNewton iterationisogeniesSchoof-Elkies-Atkin algorithm

Mathematics Subject Classification ID

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

Related Items (32)

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

Uses Software

• NTL

Cites Work

• 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
• 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?

This page was built for publication: Fast algorithms for computing isogenies between elliptic curves