Abstract:

Given ordinary elliptic curves E and E' over a finite field $\mathbb{F} _q$, this paper discusses the problem of determining for which $k\in\mathbb{N}$ it holds that $E(\mathbb{F} _{q^k})\cong E'(\mathbb{F} _{q^k})$.

Isomorphic Groups of Rational Points of Elliptic Curves over Finite Fields

Justin T Miller

jmiller@math.arizona.edu

Let $\mathbb{F} _q$ be the finite field with q=pⁿ elements, where p is prime, and let E be an elliptic curve over $\mathbb{F} _q$. If the group $E(\mathbb{F} _q)$ has order m then the group $E(\mathbb{F} _{q^k})$ has order $1+q^k-\alpha^k-\beta^k$, where $\alpha$ and $\beta$ are reciprocals of the roots of the polynomial 1-(q+1-m)x+qx². Thus, the order of an elliptic curve over a finite field determines the order of the curve over every extension of the field. More generally, one might ask if the group structure of $E(\mathbb{F} _q)$ determines the group structure of $E(\mathbb{F} _{q^k})$. The answer to this question is, in general, negative. The smallest such example occurs over $\mathbb{F} _7$. Over $\mathbb{F} _7$ the four elliptic curves defined by the equations
$$\begin{align*}E_1: & ~y^2 = x^3+5 \\ E_2: & ~y^2 = x^3+3x+5 \\ E_3: & ~y^2 = x^3+5x+5 \\ E_4: & ~y^2 = x^3+6x+5, \end{align*}$$
are precisely those with order seven. They all have the same group structure over $\mathbb{F} _7$, namely $E_1(\mathbb{F} _7)\cong\cdots\cong E_4(\mathbb{F} _7)\cong\mathbb{Z} /7\mathbb{Z}$, but over $\mathbb{F} _{49}$, $E_1(\mathbb{F} _{49})\cong\mathbb{Z} /3\mathbb{Z}\oplus\mathbb{Z} /21\mathbb{Z}$ and $E_2(\mathbb{F} _{49})\cong E_3(\mathbb{F} _{49})\cong E_4(\mathbb{F} _{49})\cong\mathbb{Z} /63\mathbb{Z}$. Here ``smallest'' refers to the order of a field $\mathbb{F} _q$ for which there are two elliptic curves E and E' with $E(\mathbb{F} _q)\cong E'(\mathbb{F} _q)$ and $E(\mathbb{F} _{q^2})\ncong E'(\mathbb{F} _{q^2})$. Despite the preceding example, the order of an elliptic curve does sometimes determine its group structure, so a first attempt to determine when $E(\mathbb{F} _q)$ determines $E(\mathbb{F} _{q^k})$ might involve finding the cases when the order of an elliptic curve determines its group structure. If E is an elliptic curve over $\mathbb{F} _q$ with $\vert E(\mathbb{F} _q)\vert=m$ and t=q+1-m, then the group structure is completely determined or has a short list of possibilities depending on t. In the cases, where q=pⁿ:
$$\begin{align*}\mbox{(i)} & ~t=\pm\sqrt{q},~2\vert n~\mbox{or}~3\nmid p-1 \\ \... ...ii)} & ~t=0,~(2\nmid n~\mbox{or}~4\nmid p-1)~\mbox{and}~4\nmid q-3 \end{align*}$$
the group $E(\mathbb{F} _q)$ is cyclic, and when $t=\pm 2\sqrt{q}$, with n even, $E(\mathbb{F} _q)\cong(\mathbb{Z} /(\sqrt{q}\pm1)\mathbb{Z} )^2$. These are the cases when the structure of $E(\mathbb{F} _q)$ is completely determined [3]. The two remaining cases are (t,q)=1 and $t=0,(2\nmid n$ or $3\nmid p-1)$ and $q\equiv 3\mod 4$. In the latter case Schoof proved in [3] that $E(\mathbb{F} _q)$ is cyclic or isomorphic to $\mathbb{Z} /2\mathbb{Z}\oplus \mathbb{Z} /\frac{q+1}{2}\mathbb{Z}$, and the possibilities for the former case were enumerated independently by both Rück and Voloch in [2] and [4], respectively. For a prime r and integer a let v_r(a) be the integer such that $r^{v_r(a)}~\Vert ~a$. Then Rück and Voloch showed that when (t,q)=1 the possibilities for $E(\mathbb{F} _q)$ are

$$\mathbb{Z} /p^{v_p(m)}\mathbb{Z}\oplus\bigoplus_{ \begin{suba... ...bb{Z} /r^{i_r}\mathbb{Z}\oplus\mathbb{Z} /r^{j_r}\mathbb{Z} ,$$

where i_r+j_r=v_r(m) and $\min(i_r,j_r)\leq v_r(q-1)$. Given the formula for $\vert E(\mathbb{F} _q)\vert$ above, if $E(\mathbb{F} _q)$ is determined by its order there is no apparent method for determining whether $E(\mathbb{F} _{q^k})$ is also determined by its order. Thus, a slightly different approach is needed.

Question 1   Given that $E(\mathbb{F} _q)\cong E'(\mathbb{F} _q)$, for which k is it true that $E(\mathbb{F} _{q^k})\cong E'(\mathbb{F} _{q^k})$?

It is well-known that the ring of endomorphisms of an elliptic curve, $\text{End}(E)$, is either an order in an imaginary quadratic field or an order in a definite quaternion algebra. The rest of this paper, for simplicity, will deal only with the former case--the ordinary elliptic curves. This is convenient, since in the ordinary case, $\text{End}(E)$ consists of the endomorphisms of E defined over $\mathbb{F} _q$. By a theorem of Lenstra, the structure of $\text{End}(E)$ determines the structure of $E(\mathbb{F} _{q^k})$ for all $k\in\mathbb{N}$ [5]. That is,

Theorem 1   Let $R=\text{End}(E)$ and let $\pi_q\in R$ be the Frobenius endomorphism, i.e. $\pi_q(x,y)=(x^q,y^q)$ for $x,y\in\overline{\mathbb{F} _q}$. Then $E(\mathbb{F} _{q^k})\cong R/(\pi_q^k-1)$ for all $k\in\mathbb{N}$.

If R is an order in an imaginary quadratic field $\mathbb{Q} (\sqrt{d})$, then $R\cong\mathcal{O}_g := \mathbb{Z} +g\mathcal{O}_K$ for some integer g>0, where $\mathcal{O}_K$ is the ring of integers in $\mathbb{Q} (\sqrt{d})$. Therefore, if $\text{End}(E)\cong\mathcal{O}_g$ and $\text{End}(E')\cong\mathcal{O}_{g'}$ then the Question 1 becomes: given $\mathcal{O}_g/(\pi_q-1)\cong\mathcal{O}_{g'}/(\pi_q-1)$, for which k does it hold that $\mathcal{O}_g/(\pi_q^k-1)\cong\mathcal{O}_{g'}/ (\pi_q^k-1)$? To answer this question, the quadratic field $\mathbb{Q} (\sqrt{d})$ must first be known.

Theorem 2   Let $\vert E(\mathbb{F} _q)\vert=m$ and d=(q+1-m)²-4q. Then d<0, $\text{End}(E)$ is isomorphic to an order in $\mathbb{Q} (\sqrt{d})$, and $\pi_q\in\text{End}(E)$ corresponds to $\frac{1}{2}(q+1-m+\sqrt{d})$ under this isomorphism.

Let d=f²d' where d' is square-free and define

$$\omega = \begin{cases} \sqrt{d'}, &\text{if $d'\equiv 2,3... ...}(1+\sqrt{d'}), &\text{if $d'\equiv 1\mod 4$ }. \end{cases}$$

Then $\{1,\omega\}$ is a basis for $\mathcal{O}_K$ as a $\mathbb{Z}$-module, and $\pi_q=a_1+f_1\omega$ where

$$\begin{cases} a_1=\frac{1}{2}(q+1-m),~f_1=\frac{1}{2}f, &\t... ...+1-m-f),~f_1=f, &\text{if $d'\equiv 1\mod 4$ }. \end{cases}$$

If $\text{End}(E)\cong\mathcal{O}_g$ then $\mathbb{Z} [\pi_q]=\mathbb{Z}\oplus\mathbb{Z} f_1\omega=\mathcal{O}_f$ and $\pi_q\in\mathcal{O}_g$, so g | f₁. Let $\pi_q^k=a_k+f_k\omega$. By direct calculation $(\pi_q^k-1)=(a_k-1,f_kgd')\mathbb{Z}\oplus(a_k-1,f_k/g)\mathbb{Z} g\omega$ or $(\pi_q^k-1)=(a_k-1,f_kg(d'-1)/4)\mathbb{Z}\oplus (a_k-1,f_k/g)\mathbb{Z} g\omega$ in $\mathcal{O}_g$ for $d'\equiv 2,3\mod 4$ or $d'\equiv 1\mod 4$, respectively. Since (a_k-1,f_k/g)=(a_k-1,f_k)/(a_k-1,g), this proves, by Theorem 1:

Theorem 3   If E and E' are elliptic curves over $\mathbb{F} _q$ with $End(E)\cong\mathcal{O}_g$ and $End(E')\cong\mathcal{O}_{g'}$, then $E(\mathbb{F} _{q^k})\cong E'(\mathbb{F} _{q^k})$ if and only if (a_k-1,g)=(a_k-1,g').

Since,

$$a_{k+1} = \begin{cases} a_ka_1+f_kf_1d', &\text{if $d'\eq... ...+f_kf_1(d'-1)/4, &\text{if $d'\equiv 1\mod 4$ } \end{cases}$$

and,

$$f_{k+1} = \begin{cases} a_1f_k+a_kf_1, &\text{if $d'\equi... ...k+f_1(a_k+f_k), &\text{if $d'\equiv 1\mod 4$ }, \end{cases}$$

Theorem 3 provides a way to answer the question above for all k below an arbitrarily high bound; however, an answer in closed form is more desireable. A sufficient condition for $E(\mathbb{F} _{q^k})\cong E'(\mathbb{F} _{q^k})$ is the following, where $\text{End}(E)\cong\mathcal{O}_g$, $\text{End}(E')\cong\mathcal{O}_{g'}$, and where $N(\alpha)$ is the norm of $\alpha$ in $\mathcal{O}_K$.

Theorem 4   If $N(\pi_q^k-1)$ is relatively prime to g and g', then $E(\mathbb{F} _{q^k})\cong E'(\mathbb{F} _{q^k})$.

This theorem can be refined by replacing g and g' with g/(g,g') and g'/(g,g'), respectively, and it also remains true if $N(\pi_q^k-1)$ is replaced by $Tr(\pi_q^k-1)$, where $Tr(\alpha)$ is the trace of $\alpha$ in $\mathcal{O}_K$. Since $(a,b)=1 \Leftrightarrow a\mathbb{Z} +b\mathbb{Z} =\mathbb{Z} \Leftrightarrow a\mathcal{O}_K+b\mathcal{O}_K=\mathcal{O}_K$, the preceding theorem suggests studying the ideal theory for orders in quadratic fields, to answer the Questionrefq:one. To sketch a proof of the previous theorem using ideal theory let $(\pi_q^k-1)_g$ denote the principal ideal $(\pi_q^k-1)\mathcal{O}_g$ of $\mathcal{O}_g$. Since $\mathcal{O}_K$ is a Dedekind domain, $(\pi_q^k-1)_1=\prod_{i=1}^{\ell}\mathfrak{p_i} ^{e_i}$ for some prime ideals $\mathfrak{p_i}$. It is proved in [1, Proposition 7.20(a)] that if $\mathfrak{a}$ is an $\mathcal{O}_K$-ideal prime to g then $\mathfrak{a}\cap\mathcal{O}_g$ is an $\mathcal{O}_g$-ideal prime to g (i.e., $\mathfrak{a\cap\mathcal{O}_g} +g\mathcal{O}_g=\mathcal{O}_g$), so $(\pi_q^k-1)_g=\prod_{i=1}^{\ell}\mathfrak{p_i} ^{e_i}\cap\mathcal{O}_g$. If the hypothesis of Theorem 4 is satisfied, then the ideals $(\pi_q^k-1)_g$ and $(\pi_q^k-1)_{g'}$ have the ``same'' factorizations in their orders, so $\mathcal{O}_g/(\pi_q^k-1)_g\cong\mathcal{O}_{g'}/(\pi_q^k-1)_{g'}$. Another related question whose solutions seem tractable using ideal theory is the following:

Question 2   Given $\mathcal{O}_g$ and $\mathcal{O}_{g'}$, is there a finite set $M\subseteq \mathbb{N}$ such that $\mathcal{O}_g/(\pi_q^k-1)\cong\mathcal{O}_{g'}/ (\pi_q^k-1)$ for all $k\in M$ if and only if $\mathcal{O}_g\cong\mathcal{O}_{g'}$?

In general, such a set does not necessarily exist, and a counterexample of this was given in [5]. The author showed that over $\mathbb{F} _{73}$ the two elliptic curves given by
$$\begin{align*}E: &~y^2=x^3+25x \\ E': &~y^2=x^3+53x+55 \end{align*}$$
have $\mathbb{Z} [i]$ and $\mathbb{Z} [2i]$ as their endomorphism rings, respectively, but $E(\mathbb{F} _{q^k})\cong E'(\mathbb{F} _{q^k})$ for all $k\in\mathbb{N}$. If, however, $\mathcal{O}_g/(\pi_q^k-1)\ncong\mathcal{O}_{g'}/(\pi_q^k-1)$ for some k, then the singleton set $\{k\}$ satisfies the conditions for M in the question. Thus, the Question 2 is equivalent to asking if there is a k such that $\mathcal{O}_g/(\pi_q^k-1)\ncong\mathcal{O}_{g'}/(\pi_q^k-1)$. A more interesting question, whose aim is similar to the previous question, is the following:

Question 3   Given $\mathcal{O}_g$ and $\mathcal{O}_{g'}$, is there an integer r and a set $M\subseteq \{0,1,~\ldots,r-1\}$ such that $\mathcal{O}_g/(\pi_q^k-1)\cong\mathcal{O}_{g'}/ (\pi_q^k-1)$ if and only if $(k\mod r)\in M$?

Empirical evidence suggests that such a set always exists. For instance, in the counter example above, r=2 and $M=\{0,1\}$ would suffice, and over small finite fields r=2 and $M\subseteq\{0,1\}$ usually will do. For some reason, a larger r and M are necessary when $\vert E(\mathbb{F} _q)\vert=m$ is a Cuban prime, that is, a prime of the form 3x²+3x+1 (e.g, 7,19,37,61,127,271,$\ldots$). For example, when $\vert E(\mathbb{F} _q)\vert=1657$, f=43 and for the orders $\mathcal{O}_{1}$ and $\mathcal{O}_{43}$, r=23 and $M=\{1,2,~\ldots,22\}$. The questions above remain open-ended, and the author will continue pursuing the answers to these and related questions throughout the next semester, using an ideal theoretic approach.