Theorem 4.2.2 ([HW79, Theorem 102]) Let n = 2e R + 1 with e ≥ 2 and R <

2e . Furthermore, let n satisfy ( n ) = ’1 for some odd number p. Then a necessary

p

and su¬cient condition for n to be prime is that p(n’1)/2 ≡ ’1 (mod n).

Proof: If n is prime, then p(n’1)/2 (mod n) ≡ ( n ) = ’1 per de¬nition of the

p

Jacobi symbol. Since

√

√

2e R + 1 > R2 + 1 > R,

n=

the other half of the theorem follows directly from Proposition (4.2.1).

Note that Hardy and Wright state a slightly di¬erent version of this theorem.

They only look at odd prime numbers p. Here the Jacobi symbol is used, which

coincides with the Legendre symbol if p is a prime.

More general than Proth™s test is the following well-known theorem:

Theorem 4.2.3 (Pocklington) Let n be a natural number and suppose that n ’

1 = F R, where F has known prime factorization F = pe1 · · · pek and where R is

√ 1 k

relatively prime to F and less than n. If for each 1 ¤ i ¤ k there exists a number

(n’1)/pi

ai such that an’1 ≡ 1 (mod n) and gcd(ai ’ 1, n) = 1, then n is a prime.

i

Proof: The proof follows directly from the proof of Proposition 4.2.1 and the

Chinese remainder theorem.

Mersenne numbers are numbers of the form Mn = 2n ’ 1. It is easy to see that

2n ’ 1 can only be a prime if the exponent n is a prime. One of the nice things

about Mersenne prime numbers is that there exists a very e¬cient primality test

for them, namely the Lucas-Lehmer primality test. See for example [Rib96, page

92] or [Bre89, page 27]. The test is described in the following proposition for later

reference.

Proposition 4.2.4 Consider the Lucas sequence {Vn (2, ’2)} (the indices (2,-2)

will be omitted from now on) de¬ned recursively by V0 = 2, V1 = 2 and Vj+1 =

2Vj + 2Vj’1 . Now Mn is prime if and only if Mn divides V(Mn +1)/2 .

A proof of this proposition can be found in either of the aforementioned refer-

ences.

4.3 Prime-generating elliptic curves 39

4.3 Prime-generating elliptic curves

Let e ≥ 1 be a natural number and E an elliptic curve de¬ned over a ¬nite ¬eld

Fq . The curve E over the extension ¬eld Fqe will also be considered. More precisely,

denote by E(Fqe ) the group of those points of E whose coordinates are contained in

the ¬eld Fqe , and denote by Ee the cardinality of this group. The following theorem

by Hasse and Weil gives some information about these numbers.

Theorem 4.3.1 (Hasse-Weil) There exists an algebraic integer ±, depending on

√

the elliptic curve E, with absolute value q such that the cardinality Ee of E(Fqe )

satis¬es

Ee = q e + 1 ’ (±e + ±e )

for all natural numbers e ≥ 1. This ± is called a Frobenius eigenvalue of the elliptic

curve E.

For a proof of this theorem, see for example page 134 of [Sil86]. Note that E(Fq ) is

a subgroup of E(Fqe ). Hence E1 divides Ee for all e.

De¬nition 4.3.2 Let E be an elliptic curve de¬ned over a ¬nite ¬eld Fq . A prime-

generating elliptic curve is a curve E such that there exist in¬nitely many prime

numbers of the form Ee /E1 .

It is unfortunately not known whether or not there exist prime-generating elliptic

curves, but some good candidates will be given later. First, the possible values of e

for which Ee /E1 can be prime will be narrowed down.

Proposition 4.3.3 Let E be an elliptic curve de¬ned over a ¬nite ¬eld Fq . Suppose

that Ee /E1 is a prime. Then one of the following statements holds:

(i) e is prime,

(ii) q = 2 and e ∈ {4, 6, 9}1 ,

(iii) q = 3 and e = 4.

Proof: Suppose that e is not a prime and let f be a non-trivial divisor of e. Then

Fqf is a non-trivial sub¬eld of Fqe . Hence E(Fqf ) is a subgroup of E(Fqe ), which

implies that Ef /E1 divides Ee /E1 . The remaining problem is to show that, except

for the last two cases mentioned in the proposition, this is a non-trivial divisor of

Ee /E1 .

Since f is a non-trivial divisor of e, it can be assumed without loss of generality

√

e ¤ f ¤ e/2. Here f denotes the ceiling function applied to

that f satis¬es

f . Hence, if either q ≥ 3 or e ≥ 5,

√

Ef ¤ ( q f + 1)2 ¤ ( q e/2 + 1)2 < ( q e ’ 1)2 ¤ Ee .

1 In [Kob01] two of these cases are missing.

40 Two families of Mersenne“like primes

To obtain the ¬rst and the last inequality, Hasse-Weil™s theorem was used. If q = 2

and e = 4, the strict inequality becomes an equality. So for q = 2 either E2 < E4

or E2 = E4 = 9.

Now the case Ef /E1 = 1 will be investigated. The relation

√

E1 ¤ ( q + 1)2 < ( q f ’ 1)2 ¤ Ef ,

holds whenever q = 2 and e > 9, or q = 3 and e > 4, or q = 4 and e > 4, or q ≥ 5.

√

Here the relation f ≥ e is used. Note that for q = 2 and e = 8 strict inequality

holds as well, since in this case f = 4.

So far it has been proven that Ef /E1 is a non-trivial divisor of Ee /E1 whenever

q = 2 and e ∈ {4, 6, 9}, or q = 3 and e = 4, or q = 4 and e = 4, or q ≥ 5.

The case q = 4 and e = 4 still has to be excluded. For E2 /E1 to be a trivial

divisor of E4 /E1 , a curve with E1 = E2 is necessary. It is not hard to see that in

this case ± = ’2 (from Hasse-Weil™s theorem), and hence E4 /E1 = 25, which is not

a prime.

Note that all of the above cases actually occur, as will be shown in Table 4.2 for

q = 2. Further note that it is not true that whenever e is a prime the number Ee /E1

is a prime as well. The situation is similar to the case of the Mersenne numbers.

Not all elliptic curves are prime-generating, as is shown in the following example.

Example 4.3.4 Consider the curve de¬ned over F4 having equation Y 2 + Y =

X 3 + ‘, where ‘ is a primitive element of F4 . In this case E1 = 1 and hence ± = 2.

Ee

This implies E1 = (2e ’ 1)2 , which obviously never is a prime number.

Up to isomorphism there exist exactly 5 elliptic curves de¬ned over F2 . As a

matter of fact their isomorphism classes can be characterized by E1 , the number

of points de¬ned over F2 . From Hasse-Weil™s theorem the relation 1 ¤ E1 ¤ 5

immediately follows. In Table 4.1 representatives of these isomorphism classes E

and their Frobenius eigenvalues ± will be listed.

E1 Weierstrass equation of E ±

Y 2 + Y = X3 + X + 1 √± i

1 1

2 3

1/2 ± i 7/2

2 Y + XY = X + X + 1 √

2 3

±i 2

3 Y +Y =X √

Y 2 + XY = X 3 + 1 ’1/2 ± i 7/2

4

Y 2 + Y = X3 + X ’1 ± i

5

Table 4.1: The non-isomorphic elliptic curves over F2 .

For which values of e the number Ee /E1 is a (probable) prime has been in-

vestigated for these ¬ve curves. Probable prime means that the number passed

two probabilistic primality tests: both the Mathematica function PrimeQ and the