Computing the endomorphism ring of an ordinary elliptic curve over a finite field

Abstract

We present two algorithms to compute the endomorphism ring of an ordinary elliptic curve E defined over a finite field F_q. Under suitable heuristic assumptions, both have subexponential complexity. We bound the complexity of the first algorithm in terms of log q, while our bound for the second algorithm depends primarily on log |D_E|, where D_E is the discriminant of the order isomorphic to End(E). As a byproduct, our method yields a short certificate that may be used to verify that the endomorphism ring is as claimed.

16 pages (minor edits)

References in corpus (4)

• Expander graphs based on GRH with an application to elliptic curve cryptography
• Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
• More Discriminants with the Brezing-Weng Method
• Computing modular polynomials in quasi-linear time

Cited by in corpus (17)

• Isogeny volcanoes
• Computing images of Galois representations attached to elliptic curves
• Class invariants by the CRT method
• Accelerating the CM method
• $\ell$-adic images of Galois for elliptic curves over $\mathbb{Q}$
• A Subexponential Algorithm for Evaluating Large Degree Isogenies
• A quasi-linear time algorithm for computing modular polynomials in dimension 2
• On the evaluation of modular polynomials
• Computing separable isogenies in quasi-optimal time
• Computing endomorphism rings of elliptic curves under the GRH
• A low-memory algorithm for finding short product representations in finite groups
• Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
• Computing supersingular endomorphism rings using inseparable endomorphisms
• Computing the endomorphism ring of an elliptic curve over a number field
• Spanning the isogeny class of a power of an ordinary elliptic curve over a finite field. Application to the number of rational points of curves of genus $\le 4$
• Hard isogeny problems over RSA moduli and groups with infeasible inversion