Next: Bibliography

### Abstract:

Given ordinary elliptic curves E and E' over a finite field , this paper discusses the problem of determining for which it holds that .

# Isomorphic Groups of Rational Points of Elliptic Curves over Finite Fields

Justin T Miller

jmiller@math.arizona.edu

Let be the finite field with q=pn elements, where p is prime, and let E be an elliptic curve over . If the group has order m then the group has order , where and are reciprocals of the roots of the polynomial 1-(q+1-m)x+qx2. 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 determines the group structure of . The answer to this question is, in general, negative. The smallest such example occurs over . Over the four elliptic curves defined by the equations

are precisely those with order seven. They all have the same group structure over , namely , but over , and . Here smallest'' refers to the order of a field for which there are two elliptic curves E and E' with and . Despite the preceding example, the order of an elliptic curve does sometimes determine its group structure, so a first attempt to determine when determines might involve finding the cases when the order of an elliptic curve determines its group structure. If E is an elliptic curve over with 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=pn:

the group is cyclic, and when , with n even, . These are the cases when the structure of is completely determined [3]. The two remaining cases are (t,q)=1 and or and . In the latter case Schoof proved in [3] that is cyclic or isomorphic to , 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 vr(a) be the integer such that . Then Rück and Voloch showed that when (t,q)=1 the possibilities for are

where ir+jr=vr(m) and . Given the formula for above, if is determined by its order there is no apparent method for determining whether is also determined by its order. Thus, a slightly different approach is needed.

Question 1   Given that , for which k is it true that ?

It is well-known that the ring of endomorphisms of an elliptic curve, , 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, consists of the endomorphisms of E defined over . By a theorem of Lenstra, the structure of determines the structure of for all [5]. That is,

Theorem 1   Let and let be the Frobenius endomorphism, i.e. for . Then for all .

If R is an order in an imaginary quadratic field , then for some integer g>0, where is the ring of integers in . Therefore, if and then the Question 1 becomes: given , for which k does it hold that ? To answer this question, the quadratic field must first be known.

Theorem 2   Let and d=(q+1-m)2-4q. Then d<0, is isomorphic to an order in , and corresponds to under this isomorphism.

Let d=f2d' where d' is square-free and define

Then is a basis for as a -module, and where

If then and , so g | f1. Let . By direct calculation or in for or , respectively. Since (ak-1,fk/g)=(ak-1,fk)/(ak-1,g), this proves, by Theorem 1:

Theorem 3   If E and E' are elliptic curves over with and , then if and only if (ak-1,g)=(ak-1,g').

Since,

and,

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 is the following, where , , and where is the norm of in .

Theorem 4   If is relatively prime to g and g', then .

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 is replaced by , where is the trace of in . Since , 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 denote the principal ideal of . Since is a Dedekind domain, for some prime ideals . It is proved in [1, Proposition 7.20(a)] that if is an -ideal prime to g then is an -ideal prime to g (i.e., ), so . If the hypothesis of Theorem 4 is satisfied, then the ideals and have the same'' factorizations in their orders, so . Another related question whose solutions seem tractable using ideal theory is the following:

Question 2   Given and , is there a finite set such that for all if and only if ?

In general, such a set does not necessarily exist, and a counterexample of this was given in [5]. The author showed that over the two elliptic curves given by

have and as their endomorphism rings, respectively, but for all . If, however, for some k, then the singleton set satisfies the conditions for M in the question. Thus, the Question 2 is equivalent to asking if there is a k such that . A more interesting question, whose aim is similar to the previous question, is the following:

Question 3   Given and , is there an integer r and a set such that if and only if ?

Empirical evidence suggests that such a set always exists. For instance, in the counter example above, r=2 and would suffice, and over small finite fields r=2 and usually will do. For some reason, a larger r and M are necessary when is a Cuban prime, that is, a prime of the form 3x2+3x+1 (e.g, 7,19,37,61,127,271,). For example, when , f=43 and for the orders and , r=23 and . 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.

Next: Bibliography
Justin MIller
2001-08-28