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

We present two algorithms to compute the endomorphism ring of an ordinary elliptic curve E defined over a finite field Fq. Under suitable heuristic assumptions, both have subexponential complexity. We bound the complexity of the first algorithm in terms of , while our bound for the second algorithm depends primarily on log|DE|, where DE 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.