HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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

Gaetan Bisson 1, 2 Andrew 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.
Document type :
Journal articles
Complete list of metadata
https://hal.inria.fr/inria-00383155
Contributor : Gaetan Bisson Connect in order to contact the contributor
Submitted on : Tuesday, May 12, 2009 - 11:14:03 AM
Last modification on : Saturday, October 16, 2021 - 11:26:06 AM

Links full text

arxiv

Identifiers

Collections

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

Citation

Gaetan Bisson, Andrew 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⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

129

 

Contact                    Legal Notice                    Personal Data