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

Gaetan Bisson 1, 2 Andrew V. Sutherland 3
1 EIPSI - Eindhoven Institute for the Protection of Systems and Information
2 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
3 Department of Mathematics [MIT]
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.
Type de document :
Article dans une revue
Journal of Number Theory, Elsevier, 2011, Elliptic Curve Cryptography, 131 (5), pp.815--831. 〈10.1016/j.jnt.2009.11.003〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00383155
Contributeur : Gaetan Bisson <>
Soumis le : mardi 12 mai 2009 - 11:14:03
Dernière modification le : mardi 18 décembre 2018 - 16:18:25

Lien texte intégral

arxiv

Identifiants

Collections

INRIA | INSMI | UNIV-LORRAINE | LORIA-ALGO | LORIA

Citation

Gaetan Bisson, Andrew V. Sutherland. Computing the endomorphism ring of an ordinary elliptic curve over a finite field. Journal of Number Theory, Elsevier, 2011, Elliptic Curve Cryptography, 131 (5), pp.815--831. 〈10.1016/j.jnt.2009.11.003〉. 〈inria-00383155〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

351

Contact


archive-ouverte@inria.fr