Paper 2009/100

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

Gaetan Bisson and Andrew V. Sutherland

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
gaetan bisson @ loria fr
History
2009-03-17: last of 2 revisions
2009-03-02: received
See all versions
Short URL
https://ia.cr/2009/100
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/100,
      author = {Gaetan Bisson and Andrew V.  Sutherland},
      title = {Computing the endomorphism ring of an ordinary elliptic curve over a finite field},
      howpublished = {Cryptology ePrint Archive, Paper 2009/100},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/100}},
      url = {https://eprint.iacr.org/2009/100}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.