International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Gaetan Bisson
Andrew V. Sutherland
Download:
URL: http://eprint.iacr.org/2009/100
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2009-18185,
  title={Computing the endomorphism ring of an ordinary elliptic curve over a finite field},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/2009/100},
  note={ gaetan.bisson@loria.fr 14301 received 26 Feb 2009},
  author={Gaetan Bisson and Andrew V. Sutherland},
  year=2009
}