and ± = 2 + ω. Using the cubic reciprocity law in the ring Z[ω] (see for example

[Cox89, pages 78-80]), it can be shown that 2 is not a cubic residue modulo EMe

(still assuming that EMe is a prime). The main fact that is used is that EMe factors

over Z[ω] as EMe = (±p ’ 1)(±p ’ 1).

Using a C program it was shown that EMe is a prime for each e in the set

{2, 5, 7, 11, 17, 19, 79, 163, 193, 239, 317, 353, 659, 709, 1049, 1103, 1759, 2029, 5153,

7541, 9049, 10453, 23743, 255361}.

In order to ¬nd the last value in the list, a modi¬ed version of Chris Nash™s

OpenPFGW C++ program was used as well as our own program. This list is

complete for values of e up to 268154.

4.5 The Wagsta¬ conjecture

The Wagsta¬ conjecture for the Mersenne numbers can be generalized to the

families of numbers arising from elliptic curves discussed in the preceding paragraph.

This was done independently in [Kob01]. The Wagsta¬ conjecture for Mersenne

numbers is the following (see [Wag83]):

Conjecture 4.5.1 (Wagsta¬ ) The distribution of Mersenne primes is character-

ized by

(i) The number of Mersenne primes less than or equal to x is approximately

(eγ / log 2) log log x. (Here γ is Euler™s constant).

(ii) The expected number of Mersenne primes 2p ’ 1 with p between n and 2n, is

approximately eγ .

(iii) The probability that 2p ’ 1 is prime, is approximately (eγ log ap)/p log 2 where

a = 2 if p ≡ 3 (mod 4) and a = 6 if p ≡ 1 (mod 4).

46 Two families of Mersenne“like primes

Although no proof of this statement is known, it is supported by the following

heuristic argument:

First recall that Mp = 2p ’ 1 can only be prime if

Heuristic argument.

p itself is a prime. According to the well-known prime number theorem (see for

instance [HW79, Theorem 6]), the probability that a random number r is prime is

asymptotically equal to 1/ log r. However, Mp is not a random number, and also

does not behave as such. Namely, if q divides Mp , then obviously 2p = 1 (mod q)

and the order of 2 modulo q divides the prime p, and thus must be equal to p. By

Fermat™s little theorem we have that the order of 2 modulo q divides q ’ 1, thus any

divisor q of Mp must be of the form q = kp + 1 where k is an integer. Also observe

that 2(q’1)/2 = 2pq = 1 (mod q), so 2 is a quadratic residue modulo q and so q must

be equal to ±1 modulo 8. Thus the smallest divisor of Mp is at least ap + 1 where

a = 2 if p is 1 modulo 4, and a = 6 if p is 3 modulo 4.

Since prime numbers q that are smaller than ap + 1 cannot divide Mp , the

1

probability that Mp is prime is enlarged by a factor of (1’1/q) for each prime q <

ap + 1. Thus an estimate of the above probability is

1 1

,

log (2p ’ 1) q<2ap+1 (1 ’ 1/q)

where the product is taken only over prime numbers q. Merten™s theorem (see for

example [BS96]) states that

n

1 pi

= eγ ,

lim

p ’1

n’∞ log n

i=1 i

where pi is the ith prime number. Thus this probability is asymptotically equal to

(eγ log ap)/p log 2. The ¬rst two claims easily follow from this observation.

For prime-generating elliptic curves Wagsta¬™s conjecture can be generalized:

Conjecture 4.5.2 Let E be a prime-generating elliptic curve de¬ned over the ¬eld

Fq . Then the following statements can be made about the distribution of the primes

generated by E:

(i) The number of primes of the form Ek /E1 less than or equal to x, is approxi-

mately (eγ / log q) log log x.

(ii) The expected number of primes of the form Ek /E1 with k between n and qn,

is approximately eγ .

(iii) The probability that Ek /E1 is prime, is approximately eγ log ak/k log q, where

a depends on the speci¬c choice of E (in general a = 2).

The a in the above conjecture is due to the fact that for all prime divisors d of

Ee /E1 we have d ≡ 1 (mod ae), if e is odd and q is not too large [Bee01, Theorem

4.5 The Wagsta¬ conjecture 47

5.3.2]. In general, a = 2 gives a sharp bound. However, for some speci¬c curves this

bound can be improved, as is shown for the two families of Mersenne-like numbers

in the next proposition.

Proposition 4.5.3 Let e be an odd prime larger than 3. Then the following state-

ments hold:

2

(i) Suppose that l is a prime divisor of the number GMe = 2e ’ 2(e+1)/2 + 1.

e

Then l ≡ 1 (mod 4e).

3

(ii) If l is a prime divisor of the number EMe = 3e ’ 3(e+1)/2 + 1, we have

e

that l ≡ 1 (mod 6e).

Proof: Note that GMe is a divisor of 22e + 1. This implies that 22e ≡ ’1 (mod l).

Hence the multiplicative order of 2 in the group F— is a divisor of 4e. This implies

l

after some manipulation of the formulas that the multiplicative order of 2 equals

4e. Thus l ≡ 1 (mod 4e). For the other half of the proposition, note that EMe is a

divisor of 33e + 1 and proceed analogously.

E pn

logq logq

E1

20

15

10

5

n

10 20 30 40

Mersenne primes

Gauss-Mersenne primes

Eisenstein-Mersenne primes

”” Wagsta¬ conjecture

Figure 4.1: Generalized Wagsta¬™s conjecture

Table 4.2 and the results concerning the Mersenne-like primes found in the pre-

vious section give an idea of how accurate both Wagsta¬™s conjecture and its gen-

eralization are. De¬ne pn to be the n-th number in the respective family such that

48 Two families of Mersenne“like primes

Epn /E1 is a prime and suppose that the elliptic curve is de¬ned over Fq . Accord-

ing to Wagsta¬™s conjecture the plot of n against logq (logq (Epn /E1 )) should lie

on a straight line with slope e’γ . In this way the accuracy of Conjecture 4.5.2

can be observed graphically. In Figure 4.1 a line with slope e’γ and the points

(n, log2 (log2 (GMpn ))) have been drawn. The respective points for the (currently)

known Mersenne primes Mp and the (currently) known Eisenstein-Mersenne primes

EMp are included in the ¬gure as well.