Computing endomorphism rings of elliptic curves under the GRH

Abstract

We design a probabilistic algorithm for computing endomorphism rings of ordinary elliptic curves defined over finite fields that we prove has a subexponential runtime in the size of the base field, assuming solely the generalized Riemann hypothesis. Additionally, we improve the asymptotic complexity of previously known, heuristic, subexponential methods by describing a faster isogeny-computing routine.

11 pages, 1 figure

References in corpus (3)

• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Expander graphs based on GRH with an application to elliptic curve cryptography
• Linearizing torsion classes in the Picard group of algebraic curves over finite fields

Cited by in corpus (3)

• Isogeny volcanoes
• Computing images of Galois representations attached to elliptic curves
• Computing the endomorphism ring of an elliptic curve over a number field