Computing the endomorphism ring of an ordinary elliptic curve over a finite field
Authors:
- Gaetan BissonGBGaetan Bisson
- Andrew V. SutherlandASAndrew V. Sutherland
Preprint
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.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Computing Hilbert class polynomials with the Chinese remainder theoremMathematics of Computation, 2010
- Primes of the Form x2 + ny21997
- Counting points on elliptic curves over finite fieldsJournal de Théorie des Nombres de Bordeaux, 1995
- Factoring Integers with Elliptic CurvesAnnals of Mathematics, 1987
- Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms.Mathematics of Computation, 1987
- On the coefficients of the transformation polynomials for the elliptic modular functionMathematical Proceedings of the Cambridge Philosophical Society, 1984
- On a problem of Oppenheim concerning “factorisatio numerorum”Journal of Number Theory, 1983