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

Let \(\mathbb F_q\) be a finite field with \(q\) elements and \(E\) be an ordinary elliptic curve defined over \(\mathbb F_q\). The endomorphism ring of \(E\) is isomorphic to an order \(O(E)\) of an imaginary quadratic field \(K\). Let \(\pi\) be the Frobenius endomorphism of \(E\) and \(t\) be its trace. If \(\big|E(\mathbb F_q)\big|\) is the order of the group of the rational points of \(E\) over \(\mathbb F_q\), one has \[ t=q+1-\big|E(\mathbb F_q)\big|. \] Let us denote by \(O_K\) the ring of integers of \(K\) and \(D_K\) its discriminant. Then \(\pi\) may be interpreted as an element of \(O_K\) of norm \(q\), and we have the equality \[ \pi={t+v\sqrt{D_K}\over 2}\quad \text{with}\quad 4q=t^2-v^2D_K. \] One has the inclusions \[ \mathbb Z[\pi]\subseteq O(E)\subseteq O_K. \] Consequently, there are only finitely many possibilities for \(O(E)\). The discriminant of \(O(E)\) is of the form \(u^2D_K\), where \(u\) divides \(v\) and uniquely determines \(O(E)\). In his paper, the author presents two algorithms to compute \(u\) i.e. \(O(E)\). Under suitable heuristic assumptions, both have subexponential complexity. His method also gives a certificate in order to verify that \(O(E)\) is as found by the algorithms.