inria-00383155, version 1
Computing the endomorphism ring of an ordinary elliptic curve over a finite field
Gaetan Bisson
1, 2Andrew V. Sutherland a, 3
Journal of Number Theory 131, 5 (2011) 815--831
Résumé : 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.
- a – Massachussetts Institute of Technology (MIT)
- 1 : Eindhoven Institute for the Protection of Systems and Information (EIPSI)
- Technische Universiteit Eindhoven
- 2 : CARAMEL (INRIA Nancy - Grand Est / LORIA)
- INRIA – CNRS : UMR7503 – Université de Lorraine
- 3 : Department of Mathematics [MIT]
- Massachussetts Institute of Technology (MIT)
- Domaine : Mathématiques/Théorie des nombres
- inria-00383155, version 1
- http://hal.inria.fr/inria-00383155
- oai:hal.inria.fr:inria-00383155
- Contributeur : Gaetan Bisson
- Soumis le : Mardi 12 Mai 2009, 11:14:03
- Dernière modification le : Lundi 14 Février 2011, 18:30:08
Documents associés
Exporter