8 Elliptic Curve Cryptography

8.1 The ElGamal and Elliptic Curve Encryption System

The standard public key systems that we have described so far, Diffie-Hellman, ElGamal, RSA and Rabin, require very large key spaces. In an attempt to use the same ideas but reduce the key space size it was suggested that Diffie-Hellman be applied to other abelian groups. To accomplish this, algebraic geometry was introduced into cryptography. In 1985, Neil Koblitz, and independently Victor Miller, suggested the use of elliptic curves over finite fields, and their corresponding groups, as possible cryptographic platforms. These methods have been quite successful and result, in many cases, in faster encryption and smaller key spaces than standard RSA methods. First, let us recall the basic ElGamal system and then we must introduce elliptic curves.

In 1984, T. ElGamal devised a method to turn the Diffie-Hellman key exchange protocol into a public key encryption protocol. This is now known as ElGamal encryption. We discussed this in detail in Section 6.4. The basic scheme for an ElGamal encryption system is the following. Each user chooses a large primep and a generator g for the cyclic group . Given a large prime p there is a fixed efficiently invertible procedure to encrypt a plaintext into residue classes within , the unit group within _p. Although each user may choose different primes this procedure is known once p is known.

For each message transmission the user’s public key is (p, g, A) where A = g^a for some integer a.

The encryption and decryption works as follows. Suppose that Bob wants to send a message to Alice. Alice’s public key, which is public knowledge, is (p, g, A) as above. The message is m and, as above, is encrypted in some workable efficient manner within , that is the message is encrypted in a manner known to all users (once p is given) as an integer in 0,1,…, p − 1. Bob now randomly chooses an integer b and computes B = g^b. He now sends (B, mC) to Alice where C = g^ab. Notice that C is the common shared key in the Diffie-Hellman key exchange and in the encryption this is multiplied by the message m.

To decrypt Alice first uses B to determine the common shared key C. Since B = g^b and she knows A = g^a she knows C = g^ab for the same reasons as the Diffie-Hellman key exchange works. Since she knows C = g^ab and she knows the modulus p she can compute the inverse g^−(ab). This is efficient since it only requires one exponentiation modulo p. She then multiplies mC = mg^ab by g^−ab to obtain the message m.

Although ElGamal proposed using the cyclic groups for large primes p, this type of encryption can be used in any cyclic group where the discrete log problem is assumed hard. If the group is a cyclic group within the group of an elliptic curve, ElGamal encryption becomes the basis for elliptic curve cryptography. Before dis cussing elliptic curve cryptography in detail, we must introduce the necessary algebraic geometric material concerning elliptic curves.

8.2 Elliptic Curves

We start with a fixed finite field F of characteristic not equal to 2 or 3. For cryptographic purposes an elliptic curve over F consists of the points (x, y) ϵ F² satisfying the equation

C : y² = x³ + ax + b; a, b ϵ F

together with a distinguished point at infinity denoted by . A group operation can be placed on the points on C to form an abelian group, usually denoted E(C), called the elliptic curve group over C. There must be additional conditions met by the elliptic curve C to be useful in cryptography and we will discuss these later.

The standard public key cryptographic protocols such as Diffie-Hellman, ElGamal and RSA use as platforms the cyclic groups in modular rings and, as explained in Chapter 6, are based on supposedly hard number theoretic problems. Miller and Koblitz noted that these problems are also difficult in elliptic curve groups. Hence the methods of public key encryption and key exchange, embodied in the above protocols, can be mimicked with some great advantages within the groups of elliptic curves. The use of elliptic curve RSA encryption is basically of only theoretical interest since the difficulty of the factoring problem turns out to be equally difficult in number theory and elliptic curves. However, the discrete log problem, and hence Diffie-Hellman and ElGamal, provides a distinct advantage for elliptic curve groups.

Before introducing elliptic curve cryptography, we discuss the algebraic preliminaries necessary for the study of elliptic curves.

8.2.1 Fields and Field Extensions

Elliptic curve cryptography involves elliptic curves over finite fields. We first look at the necessary material from fields and field extensions. For more details and proofs see the book [CFR1].

Recall that a field F is a commutative ring with an identity such that every nonzero element has a multiplicative inverse (see [CFR1]). The rationals , the reals and the modular rings _p, where p is a prime, all form fields.

The characteristic of a field F denoted char(F) is the smallest n ϵ such that n · 1 = 0. If no such n exists then the characteristic is zero. It is clear that the characteristic of is 0. Further if p is a prime the characteristic of the finite field _p is p. Since there are no zero divisors (non-zero elements whose product is zero) in a field we get the following.

Theorem 8.2.1. The characteristic of a field is zero or a prime.

If a field F has characteristic zero then it must be infinite. Hence if F is a finite field its characteristic must be a prime p.

Lemma 8.2.2. If F is a finite field then char(F) = p for some prime p.

A field F is a prime field if its only non-trivial subfield is the field itself. It is easy to show that the rationals and the finite fields _p are prime fields. However, the real number field is not a prime field.

If F and F′ are fields with F a subfield of F′, then F′ is an extension field, or field extension, or simply an extension, of F · F′ is then a vector space over F and the degree of the extension is the dimension of F′ as a vector space over F. We denote the degree by |F′: F|. If the degree is finite, that is, |F′: F| < ∞, so that F′ is a finitedimensional vector space over F, then F′ is called a finite extension of F.

From vector space theory we easily obtain that the degrees are multiplicative. Specifically:

Lemma 8.2.3. If F ⊂ F′ ⊂ F″ are fields with F″ a finite extension of F then |F″: F′| and |F″: F| are also finite, and |F″: F′| = |F″: F′| |F′: F|.

In the case of the lemma we say that F′ is an intermediate field (when F and F″ are understood) and F is the ground field.

Lemma 8.2.4. The field is a finite extension of , but the field is an infinite extension of .

The elements 1, i form a basis for over . Hence the dimension over is 2 and is a finite extension of R. The fact that | : | is infinite can be shown using the existence of transcendental numbers (see [CFR1]).

Let F be a field. Denote by F[x] the set of all polynomials with coefficients from F. A polynomial f (x) ϵ F[x] of degree ≥ 1 is irreducible if it cannot be factored into two polynomials each of smaller degree. A root or zero of a polynomial f (x) ϵ F[x] is an element c with f (c) = 0. If c is a root of f (x) then the linear factor x − c divides f (x).

Lemma 8.2.5. If f(x) ϵ F[x] and f(c) = 0 for c ϵ F then f(x) = (x − c) h(x) for some h(x) ϵ F[x].

Suppose F′ is an extension field of F and α ϵ F′. Then α is algebraic over F if there exists a polynomial 0 ≠ p(x) ϵ F[x] with p(α) = 0. This means that the element a is a root of a polynomial with coefficients in F. If every element of F′ is algebraic over F, then F′ is an algebraic extension of F. If α ϵ F′ is non-algebraic over F, then a is called transcendental over F. A non-algebraic extension is called a transcendental extension.

Lemma 8.2.6. Every element of F is algebraic over F.

Proof. If f ϵ F then p(x) = x− f ϵ F[x] and p(f) = 0.

The tie-in to finite extensions is via the following theorem (see [CFR1] for a proof).

Theorem 8.2.7. If F′ is a finite extension of a field F, then F′ is an algebraic extension.

If a polynomial f (x) ϵ F[x] of degree 2 or higher has a root in F then it is reducible. Hence if f (x) ϵ F[x] of degree greater than one is irreducible it cannot have root in F. The next result, due to Kronecker, is fundamental because it says that given any irreducible polynomial f (x) ϵ F[x] we can construct an extension field F′ of F in which f (x) has a root.

Theorem 8.2.8 (Kronecker’s Theorem). Let F be a field and f (x) ϵ F[x] an irreducible polynomial over F. Then there exists a finite extension F′ of F where f (x) has a root.

The proof of Kronecker’s Theorem follows from the following construction. There is a division algorithm in F[x]. Given f (x), g(x) ϵ F[x] then there exist q(x), r(x) ϵ F[x] such that

f (x) = q(x) g(x) + r(x)

where r(x) = 0 or deg r(x) < deg g(x). From this we can define the greatest common divisor or gcd of g(x), f (x) as a monic polynomial d(x) such that d(x) | g(x), d(x) | f (x) and if dx) is another common divisor of f (x) andg(x) then dx) | d(x). Then just as in the integers we get the following results (see [CFR1] for proofs).

Theorem 8.2.9. Given f (x), g(x) ϵ F[x] then their gcd exists, is unique and can be written as a linear combination, that is

d(x) = k(x) f (x) + h(x) g(x)

for some h(x), k(x) ϵ F[x].

From this we also get, using the division algorithm, that the Euclidean algorithm works, just as in the integers to find the gcd of two polynomials. We also get Euclid’s Lemma

Lemma 8.2.10. If p(x) is an irreducible polynomial and p(x) | f(x)g(x) then p(x) | f (x) or p(x) | g(x).

As a consequence we obtain that F[x] has unique factorization into irreducible polynomials, that is F[x] is a unique factorization domain. The proof follows the same general outline as the proof of the Fundamental Theorem of Arithmetic.

Theorem 8.2.11. F[x] is a unique factorization domain. That is given f (x) ϵ F[x] then f(x) can be written as a product of irreducible polynomials and this factorization is unqiue up to ordering and unit factors.

Kronecker’s Theorem follows from this construction in the following manner. If f (x) is an irreducible polynomial then

〈f (x)〉 = {g(x)f (x) | g(x) ϵ F[x]}

forms a maximal ideal in F[x] and hence K = F[x]/〈f (x)〉 forms a field. F ⊂ K and x + 〈f (x)〉 ϵ K is a root of f (x) (see [CFR1]). If we denote this root by α then K has a basis 1, α ,…,αⁿ⁻¹ as a vector space over F. Hence the degree of this extension is precisely the degree of the irreducible polynomial.

If F = _p then for each n > 1 there exists an irreducible polynomial of degree n, and hence for each n there is a finite field of size pⁿ. This can be shown to be unique up to isomorphism and is denoted _pⁿ and called the Galois field of order pⁿ, that is with pⁿ elements.

From Kronecker’s Theorem, we have seen that given an irreducible polynomial over a field F, we can always find a field extension in which this polynomial has a root. By repeating this procedure we can push this further to obtain field extensions in which a given polynomial has all its roots.

Definition 8.2.12. If 0 = f(x) ϵ F[x] and F′ is an extension field of F, thenf (x) splits in F¹ (F¹ may be F) iff(x) factors into linear factors in F′[x]. Equivalently, this means that all the roots of f (x) are in F′. F′ is a splitting field for f (x) over F if F′ is the smallest extension field of F in which f (x) splits. (A splitting field for f (x) is the smallest extension field in which f (x) has all its possible roots.) F′ is a splitting field over F if it is the splitting field for some finite set of polynomials over F.

Theorem 8.2.13. If 0 = f(x) ϵ F[x], then there exists a splitting field for f (x) overF.

Pushing this further, we can construct a field, called the algebraic closure of F, which we will denote by F, which is the smallest field where every f (x) ϵ F[x] splits. We say that such a field F′ is algebraically closed. Note that in this language the famous Fundamental Theorem of Algebra says that the complex number field C is algebraically closed. The next result gives several clearly equivalent formulations of being algebraically closed.

Theorem 8.2.14. LetF be a field. Then the following are equivalent:

(1)  F is algebraically closed.

(2)  Every non-constant polynomial f (x) ϵ F[x] splits in F[x].

(3)  F has no proper algebraic extensions, that is, there is no algebraic field extension ϵ with F c ϵ and F ≠ ϵ.

Example 8.2.15. For this example we assume the Fundamental Theorem of Algebra, that is, that C is algebraically closed. Note that C is not the algebraic closure of Q since C is not algebraic over Q. However, the field of complex algebraic numbers A_c, that is, the set of complex numbers which are algebraic over Q, is the algebraic closure of Q. To see this, notice that A_c is algebraic over Q by definition. Now we show that it is algebraically closed. Let f (x) ϵ A_c [x]. If a is a root of f (x), then a eC, and then a is also algebraic over Q since each element of A_c is algebraic over Q. Therefore, a ϵ A_c and A_c is algebraically closed.

More generally, if K is an extension field of F and K is algebraically closed, then the algebraic closure of F in K is the algebraic closure of F.

We need the following concept.

Definition 8.2.16. Let F′, F″ be extension fields of F. An F-isomorphism is an isomorphism a : F′ F″ such that a f) = f for all f ϵ F. That is, an F-isomorphism is an isomorphism of the extension fields that fixes each element of the ground field. If F′, F″ are F-isomorphic, we denote this relationship by F′ F″.

Theorem 8.2.17. Every field F has an algebraic closure, and any two algebraic closures of F are F-isomorphic.

To study elliptic curves we will need the following.

Theorem 8.2.18. LetF be a field with char(F) = 2,3 and letf(x) = x³ + ax + b ϵ F[x]. Then f(x) has three pairwise distinct zeros in the algebraic closure of F if and only if 4a³ + 27b² = 0 inF. The element

Δ = −4a³ − 27b²

is called the discriminant off (x).

The result follows from Cardano’s formula (see [CFR1]).

8.2.2 Elliptic Curves

We now introduce elliptic curves over a field F. Elliptic curves play an important role in many areas of mathematics and they were crucial in the proof, given by A.Wiles, of Fermat’s Last Theorem. In the next two sections we look at the material we need for elliptic curve cryptography. We refer to [Sil] for further information on elliptic curves in general. We consider only the case where the field F has characteristic = 2,3. In the case of characteristic 2, the considered Weierstrass form (normal form) that we will introduce shortly, is different. For information about elliptic curves over fields of characteristic 2or3, see [Sil] or [Was].

Definition 8.2.19. Let F be a field with char(F) = 2,3. Given an equation of the form

with a₁, a₂, a₃, a₄, a₆ ϵ F then the set

C(F) = {(x, y) ϵ F² | (x, y) satisfies (**)}

is called a (planar affine) cubic curve over F.

We note that the numeration of the coefficients may look a bit strange but there are historical reasons for it and it is used in the literature.

Under an appropriate coordinate transformation a cubic curve can be put into a standard form.

Theorem 8.2.20. Let F be a field with char(F) = 2,3. Then there exists a coordinate transformation

x ↦ a₁x + a₂y + a₃, y ↦ fi_xx + fi₂y + p₃

with a¡, p¡ ϵ F which carries the equation (**) into an equation of the form

y² = x³ + ax + b with a, b ϵ F.

The equation above is called the Weierstrass form of the cubic curve.

The proof is computational and uses only transformation methods from linear algebra. For the remainder of this chapter we always assume that a cubic curve is given in its Weierstrass form.

Let F be a field and F be its algebraic closure. Let C(F) : y² = x³ + ax + b be a cubic curve over F. Consider the polynomial g(x, y) = y² − x³ − ax − b in two variables over F and the corresponding extended curve

: y² = x³ + ax + b.

A point (r, s) ϵ is called a singular point if

If g(x, y) = y² − x³ − ax − b and (r, s) ϵ is a singular point then

s² − r³ − ar − b = 0, -3r² − a = 0 and 2s = 0.

It follows that a = −3r² and b = 2r³ and hence

Δ = −4a³ − 27b² = 4 · 27 · r⁶ − 4 · 27 · r⁶ = 0,

that is the discriminant Δ of x³ + ax + b is 0. We say that the cubic curve C(F) is non-singular or smooth if the extended curve C(F) has no singular point. The above calculations easily show that is smooth if and only if Δ = 0.

If Δ = 0 then the above equation defines a point (r, s) ϵ F that is singular. Combined with Theorem 8.2.2.1 we get the following.

Theorem 8.2.21. LetF be a field with char(F) = 2,3 and let C(F): y² = x³ + ax + bbe a cubic curve in Weierstrass form over F. The the following are equivalent:

(1)  The polynomial f(x) = x³ + ax + b has three pairwise distinct zeros in , the algebraic closure of F.

(2)  The discriminant Δ = −4a³ − 27b² = 0 in F,

(3)  C(F) is smooth.

Definition 8.2.22. Let F be a field with char(F) = 2,3. Then an elliptic curve is a smooth curve C(F): y² = x³ + ax + b over F.

An elliptic curve C(F) is smooth and therefore from Theorem 8.3.2 it follows that the discriminant Δ = −4a³ − 27b² = 0 and that x³ + ax + b has three distinct zeros in .

To provide an explanation of the name ellipitc curve, we briefly describe the connection with elliptic functions.

The Weierstrass p-function is defined as

where and w = mw₁ + nw₂, m, n eZ.

The function p(z) is an elliptic or doubly periodic function, that is, we have p(z + w) = p(z) for all w ϵ {mw₁ + nw₂| m, n ϵ Z}. The function p(z) satisfies the differential equation

(p’ (z))² = 4(p(z))³ − g2p(z) − g3

where g₂, g₃ are constants depending only on w₁, w₂.

Now let F = C and C(F) : y² = x³ + ax + b with -4a² - 27b² = 0 be an elliptic curve over C. Ifwereplacex by x = 475-, a by g₂ = −4^1/3a and b by −g₃ then we get

y² = 4(x)³ + 4^1/3 aX + b = 4(x)³ − g₂x − g₃.

From Δ = −4a³ − 27b² = 0 we get that g3 − 27g = 0.

There exist and a parametrization y = p’(z), x = p(z) where p(z) is the Weierstrassp-function corresponding to w₁, w₂. For more details see [Sch].

8.2.3 Elliptic Curve Groups

We will now write (F) for an elliptic curve over a field F. This implies that the curve is smooth and the discriminant is non-zero. We will add on a point at infinity with we will denote by O and denote by (F) the extended curve (F) u . On the points of the extended elliptic curve (F) we will define an addition that will make the points form an abelian group, called the elliptic curve group. It is on this group that we will construct an elliptic curve cryptosystem. If the underlying field is the reals this operation is very easily motivated by geometry so we will do this first. From the equations that arise in we will define the addition over any field F of characteristic = 2,3. Elliptic curve cryptography is usually done over a finite field.

Consider now an elliptic curve

(F) : y² = x³ + ax + b

over the real numbers and let (F) = (F) u . We will geometrically define a binary operation on (F). Now the elliptic curve is given by a curve in the complex plane. Suppose that P, Q are two points on the curve. Then we define the following:

(1)  If P = (x, y) then -P = (x, −y), and we define P + (-P) = .

(2)  If P = Q = -P then the line PQ will hit the curve at a third point R = (x, y). Let R* = (x, −y) be the reflection of R through the x-axis. Then we define P + Q = R*.

(3)  P + P = R* where we do the same procedure as when P = Q but use the tangent line at P.

(4)  P + = + P = P.

(5)   + = and −= .

These operations over can easily be put into coordinate form. Suppose P = (x_1; yj, Q = (x₂,y₂) andP + Q = (x₃,y₃). Then if P = Q, x₂ = x₁ then

If P = Q and x₂ = x_1; y₂ = y₁ then

If P = Q so (x₃, y₃) = 2P, y₁ = 0, then

IfP = Q so (x₃,y₃) = 2P, y₁ = 0 then

Now we consider an elliptic curve (F) : y² = x³ + ax + b over a finite field F with discriminant Δ = −4a³ − 27b² = 0 in F.

Theorem 8.2.23. Let F be a field with characteristic not equal 2 or 3 and let (F) be an elliptic curve over F. Let O denote the point at infinity and let (F) = (F) u O. If P₁ = (x₁, y₁) and P₂ = (x₂, y₂) with P_v P₂ = O are two points in (F) then we define the point P₁ + P₂ and −P₁ by the coordinate equations given in (*), (**), (***) and (****). Addition with O is defined to make O an additive identity. Then:

(a)  This addition is a valid binary operation of(F), that is, the addition of two points in (F) is again in (F).

(b)  The set(F) together with this operation forms an abelian group. IfF is a finite field this is then a finite abelian group.

Proof. (a) is purely computational and can be done with a suitable computer algebra system like CoCoA (see [KR1] and [KR2]).

(b)  The existence of an additive identity and inverses are built into the definition of the operation. Similarly the commutativity of the operation follows easily from the definition. The associativity of the operation can be done computationally with CoCoA. A formal theoretical proof can be found in the book by Knapp on elliptic curves [Kna].

Note that if n > 3 is an integer with (6, n) = 1 then we may consider cubic curves

C(Z_n) = {(x, y) eZ | y² = x³ + ax + b, a, b ϵ Z_n].

We call C(Z_n) an elliptic curve over Z_n if 4a³ + 27b² = 0 in Z_n. With this condition, we get that for each prime divisor p of n, the cubic curve

E_p : y² = x³ + ax + b

is a cubic curve over Z_p, if we just reduce modulo p. We may try to define an operation + as in the theorem above. Let P₁ = (x₁,y₁),P₂ = (x₂,y₂) withx₁ = x₂ or x₁ = x₂,y₁ = y₂ = 0be elements of C(Z_n). If x₁ − x₂ = 0ory₁ = 0 respectively are not invertible in Z_n, then the operation is not well-defined and n is composite. Then d = (x₁ −x₂, n) and d = (y, n) respectively are divisors of n. This is roughly the idea for the elliptic curve factorization algorithm for integers n > 1 by H. W. Lenstra [Len]. One has to start with an elliptic curve C(Z_n) : y² = x³ + ax + b which contains elements (x, y) ϵ Z; for instance with such an elliptic curve with b = 1 then (0,1) ϵ C(Z_n).

Now again let F be a finite field with char(F) = 2,3 and (F) the elliptic curve group for the elliptic curve (F). As usual we write

nP = P + P + ··· + P, n times for n eN,

P1 − P2 = P1 + (-P2),

and

(-n)P = n(-P) for n eN.

We want to use the abelian group (F) as a platform group for a public key cryptosystem based on the additive version of the discrete log problem in (F). In additive notation this is, given P and nP determine n. Constructing this cryptosystem we will do later in this chapter. Here we consider the following questions that are important for cryptographic purposes.

(1)  How can we in general find an (F) over a finite field F with enough elements?

(2)  How can we calculate the order |P| of an element P ϵ (F) with F a finite field?

(3)  How can we calculate the overall order |(F)| with F a finite field?

Before we consider these questions we give some examples.

Example 8.2.24.Let F = ₁₁ and y² = x³ + x +6. This equation defines an elliptic curve over Z₁₁ since

In a systematic manner we find that

Therefore |(₁₁| = 13. Since 13 is a prime, it follows that (₁₁) is a cyclic group generated by any non-zero element, for instance by (2,4).

Example 8.2.25.Let F = ₅ and y² = x³ + x. This equation defines an elliptic curve over ₅. Again in a systematic manner we find that

Hence

(₅) = ₂ x₂ = V₄

the Klein four group.

If we take the same equation over F = ₇ instead of ₅, then the elliptic curve group is cyclic of order 8.

These types of groups, cyclic groups and direct products of two cyclic groups, are typical for elliptic curve groups over finite fields.

8.2.4 The Order of an Elliptic Curve Group

We now present some theorems about the structure and order of elliptic curve groups over finite fields. For this section, F is a finite field, so F is the Galois field F = F_q where q = pⁿ for some prime p and n > 1. The structure and order are relevant to the answers to the questions we presented in the last section, and to the development of elliptic curve cryptosystems. For proofs we need a great deal more informations about the theory of elliptic curves and for the proofs we solely provide references.

For this section we assume that F = F_q, q = pⁿ for some prime p > 5 and n > 1. Since the multiplicative group F^* is cyclic we get

Therefore we expect about q elements in (F).

It is easy to provide an upper bound for |(F)|. Consider f(x) = x³ + ax + b. If f (x) is a square in F, that isf (x) = y² in F, then we get the two points (x, y) and (x, −y) on (F). Together with the element O we then get the upper bound |(F)| < 2q +1. A much stronger result is given by the following.

Theorem 8.2.26 (Hasse’s Theorem). Let F = F_q with q = pⁿ, p prime and n > 1 and (F): y² = x³ + ax + bbean elliptic curve. Then

A proof of Hasse’s Theorem can be found in the book by J.H. Silverman [Sil].

The number t = q + 1-|(F)| is called the trace of the Frobenius map. Wediscuss this later for the case q = p > 5. The elliptic curve (F) is called super singular if p | t. We will see later that super singular elliptic curves are not suitable for cryptographic purposes.

Theorem 8.2.27. LetF = W_qwithq = pⁿ, pprimeandn > 1. Then there exists an elliptic curve (F) with |(F)| = q +1 − t if and only if one of the following conditions hold:

(1)  t is non-congruent to 0 modulo p and |t| < 2Vq. In this case (F) is not super singular.

(2)  2 does not divide n and t = 0.

(3)  2 divides n and t = 0 and p is not congruent to 1 modulo 4.

(4)  2 divides n and t² = q and p is not congruent to 1 modulo 3.

(5)  2 divides n and t² = 4q.

A proof is given in the paper by Waterhouse [Wat].

Corollary 8.2.28. LetF = _p withpprime andp > 5. Let

Then there exists for each k ϵ I at least one elliptic curve (_p) with |(_p)| = k.

Proof. Let k = p + 1 − t ϵ I. Since q = p > 5we have |t|< p and we have to consider the cases (1) and (2) of the theorem. If t = 0 then t is non-congruent to 0 modulo p for case (1) which shows the existence for t = 0. But 2 does not divide n because n =1 which shows the existence for t = 0.

Theorem 8.2.29. Let F = F_q with q = pⁿ,p > 5 prime and n > 1 and (F) be an elliptic curve over F. Then (F) is either cyclic or the direct product (F) = C₁ x C₂ where C₁ s (_%, +) and C₂ = (_n , +) where n₁, n₂ eN with n₂|n₁ and n₂|(q − 1).

For a proof of this result see [Sil]. A proof is also available in [Sc1] where there is also a complete description of (F) in the case of a super singular curve.

If (F) is not super singular we have the following.

Theorem 8.2.30. LetF = F_q with q = pⁿ,p > 5 prime and n > 1. Letk = q + 1 − t with t not divisible by p and |t| < 2 Vq. Suppose n₁, n₂ ϵ N with k = n₁n₂, n₂ | n₁ and n₂ | (q − 1). Then there exists an elliptic curve (F) with

|(F)| = k and (F) = (_n1, +) x (_n2, +).