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

Elliptic curves over global fields (11G05) Curves over finite and local fields (11G20) Algebraic number theory computations (11Y40) Applications to coding theory and cryptography of arithmetic geometry (14G50)

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.

Review text

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.

Recommendations

Cites work

Cited in

(38)

Describes a project that uses

Uses Software

This page was built for publication: Computing the endomorphism ring of an ordinary elliptic curve over a finite field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2430982)