4.2. This table extends the table given in [Kob01] for the ¬ve curves de¬ned over

F2 .

4.4 A primality test for certain elliptic curves 41

Whether Ee /E1 is a (probable) prime has been checked for all values of e less

than or equal to 17389. Since the characteristic is 2, the only candidates for e are

prime numbers and the numbers in the set {4, 6, 9} (see Proposition 4.3.3).

The case E1 = 1 will be examined more closely in the next section.

E1 e

1 2, 3, 5, 7, 11, 19, 29, 47, 73, 79, 113, 151, 157, 163, 167, 239, 241, 283, 353, 367,

379, 457, 997, 1367, 3041, 10141, 14699

2 2, 3, 5, 7, 11, 17, 19, 23, 101, 107, 109, 113, 163, 283, 311, 331, 347, 359, 701,

1153, 1597, 1621, 2063, 2437, 2909, 3319, 6011, 12829

3 2, 3, 4, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347,

701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479

4 2, 5, 7, 9, 13, 19, 23, 41, 83, 97, 103, 107, 131, 233, 239, 277, 283, 349, 409, 571, 1249,

1913, 2221, 2647, 3169, 3527, 4349, 5333, 5903, 5923, 6701, 9127, 9829, 16187

5 4, 5, 6, 7, 9, 11, 13, 17, 29, 43, 53, 89, 283, 557, 563, 613, 691, 1223, 2731, 5147,

5323, 5479, 9533, 10771, 11257, 11519, 12583

Table 4.2: All e ¤ 17389 for which Ee /E1 is a (probable) prime.

4.4 A primality test for certain elliptic curves

If either N + 1 or N ’ 1 can be factored, there exists an e¬cient way of testing

N for primality. The numbers which will be tested have the form Ee /E1 , where E1

is some small number and Ee = q e + 1 ’ (±e + ±e ) for some complex number ± of

√

absolute value q. In general there seems no hope to factor Ee /E1 ± 1, since the

nice structure of the number Ee is lost by the division by E1 . However, for some

elliptic curves E1 is equal to 1. In the following proposition all elliptic curves with

E1 = 1 will be given.

Proposition 4.4.1 Let E be an elliptic curve de¬ned over Fq with the property that

E1 = 1. Then there are three possibilities:

(i) q = 2 and the curve E is isomorphic to the curve with Weierstrass equation

Y 2 + Y = X 3 + X + 1,

(ii) q = 3 and the curve E is isomorphic to the curve with Weierstrass equation

Y 2 = X 3 ’ X ’ 1,

(iii) q = 4 and the curve E is isomorphic to the curve with Weierstrass equation

Y 2 + Y = X 3 + ‘, where ‘ is a primitive element of F4 .

This is a well-known fact from the theory of elliptic curves. As a matter of fact

all curves de¬ned over a ¬nite ¬eld Fq whose Jacobians have exactly one Fq -rational

point have been classi¬ed (see for example [LMQ75]). Nevertheless, the proof of the

above proposition will be given for the reader™s convenience.

42 Two families of Mersenne“like primes

Proof: First, the possible Frobenius eigenvalues ± are determined. Write

± = a + bi, with a and b real numbers. Then the relation a2 + b2 = q holds

by Hasse-Weil™s theorem. Further, the assumption E1 = 1 implies the equation

a = q/2. Hence b2 = q ’ q 2 /4. Since b2 ≥ 0, this implies q ∈ {2, 3, 4}. This gives

rise to the three cases mentioned in the proposition.

Note that for all of the three cases mentioned above, ± + ± = q, so the three

curves are supersingular. We shall now determine the numbers Ee for these three

cases.

Proposition 4.4.2 Let E be the elliptic curve de¬ned over F2 with Weierstrass

equation Y 2 + Y = X 3 + X + 1. Then the Frobenius eigenvalues are given by 1 ± i.

Furthermore

2 ’ 2e/2+1 + 1

±e

e≡0

if (mod 8),

e

2 ’ 2(e+1)/2 + 1 e ≡ 1, 7

if (mod 8),

Ee = 2e + 1 e ≡ 2, 6

if (mod 8),

2 + 2(e+1)/2 + 1

e

e ≡ 3, 5

if (mod 8),

e

2 + 2e/2+1 + 1 e≡4

if (mod 8).

Let E be the elliptic curve de¬ned over F3 with Weierstrass equation Y 2 = X 3 ’X’1.

√

Then the Frobenius eigenvalues are given by (3 ± i 3)/2 and

±e e/2

3 ’2·3 +1 e≡0

if (mod 12),

e

3 ’ 3(e+1)/2 + 1 e ≡ 1, 11

if (mod 12),

e

3 ’ 3e/2 + 1 e ≡ 2, 10

if (mod 12),

Ee = 3e + 1 e ≡ 3, 9

if (mod 12),

3 + 3e/2 + 1

e

e ≡ 4, 8

if (mod 12),

3 + 3(e+1)/2 + 1

e

e ≡ 5, 7

if (mod 12),

e

3 + 2 · 3e/2 + 1 e≡6

if (mod 12).

Let E be the elliptic curve de¬ned over F4 with Weierstrass equation Y 2 +Y = X 3 +‘,

where ‘ is a primitive element of F4 . Then the Frobenius eigenvalue is given by 2

and the number of F4 -rational points satis¬es

Ee = 4e ’ 4(e+1)/2 + 1 = (2e ’ 1)2 .

Proof: The results follow directly from Theorem 4.3.1.

The third curve can never give (new) primes, since Ee is the square of a Mersenne

number for any e (see Example 4.3.4). For the ¬rst two curves the following corollary

is stated:

Corollary 4.4.3 Let e be a prime not equal to 2 or 3. Then Ee = 2e ’ 2 2(e+1)/2 +

e

1 for the ¬rst curve in Proposition 4.4.2. For the second curve in Proposition 4.4.2,

Ee = 3e ’ 3 3(e+1)/2 + 1. Here 2 and 3 denote Legendre symbols.

e e e

4.4 A primality test for certain elliptic curves 43

These numbers can be viewed as an equivalent of Mersenne numbers in the ring

of Gaussian (respectively Eisenstein) integers, hence the following names:

De¬nition 4.4.4 Let e be an odd prime. De¬ne the Gauss-Mersenne number GMe

as

2

GMe = 2e ’ 2(e+1)/2 + 1,