and the Eisenstein-Mersenne number EMe as

3

EMe = 3e ’ 3(e+1)/2 + 1.

e

For these two numbers, GMe ’ 1 (respectively EMe ’ 1) can be factored easily to

such an extent that a primality test for the numbers GMe and EMe immediately

follows:

prime and n ≥ 2. De¬ne

Theorem 4.4.5 Let e be an odd

±

if e ≡ 5, 7

3 (mod 8),

if e ≡ 3

a= 5 (mod 8),

2n

if e ≡ 2n+1 + 1 (mod 2n+2 ).

2 +1

The number GMe is a prime if and only if

a(GMe ’1)/2 ≡ ’1 (mod GMe ).

Proof: According to Theorem 4.2.2, the only thing that has to be shown is that

GMe

= ’1. However, this follows immediately by repeatedly using the quadratic

a

reciprocity law for Jacobi symbols. In the case e ≡ 7 (mod 8) we have

e+1

2e ’ 2

GMe +1 3 3

2

= = = ,

e+1

2’1+1

a 3 2e ’ 2 +1

2

because if we set e = 7 + 8k we get 27+8k ≡ 27 28k ≡ 128256k ≡ 2 (mod 3) and

24+4k ≡ 24 24k ≡ 1616k ≡ 1 (mod 3). So

GMe 3

= ’1.

=

a 2

When e ≡ 5 (mod 8) we have

e+1

2e + 2

GMe +1 3 3

2

=’ =’

= ,

e+1

2’2+1

a 3 2e + 2 +1

2

44 Two families of Mersenne“like primes

since writing e = 5 + 8k yields 25+8k ≡ 25 28k ≡ 32256k ≡ 5 (mod 3) and 23+4k ≡

23 24k ≡ 816k ≡ 2 (mod 3). So

GMe 3

=’ = ’1.

a 1

If e ≡ 3 (mod 8), the relation

e+1

2e + 2

GMe +1 5 5

2

= = =

e+1

a 5 3+4+1

2e + 2 +1

2

holds, since if we write e = 3 + 8k we have 23+8k ≡ 23 28k ≡ 3256k ≡ 3 (mod 5) and

22+4k ≡ 22 24k ≡ 416k ≡ 4 (mod 5). Thus

GMe 5 3 3

= ’1.

= = =

a 3 5 2

Lastly, if e ≡ 1 (mod 8) there exists an integer n ≥ 1, such that e ≡ 2n+1 + 1

(mod 2n+2 ). Then

e+1 n n

2e ’ 2 2 + 1 22 + 1 22 + 1

GMe

= ’1,

= = =

22n + 1 22n ’ 22n + 1

e+1

a 2e ’ 2 +1

2

since e > (e + 1)/2 > 2n .

To perform this primality test e squarings and 1 multiplication modulo GMe

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

has to be computed since a(GMe ’1)/2 = (a2 a±1 )2 . Since a squaring

takes far more work than an addition, additions will be ignored in this estimate.

The modular reduction can be implemented in a few additions because of the special

form of the numbers. Therefore the computational complexity of this primality test

is O(log2 (GMe )) squarings.

Now the computational complexity of the Lucas-Lehmer test will be considered.

The primality test of Proposition 4.2.4 can be rewritten as follows:

Proposition 4.4.6 De¬ne the sequence {sn } inductively by s1 = 4 and sn+1 =

s2 ’ 2. For an odd prime p the Mersenne number Mp = 2p ’ 1 is a prime if and

n

only it divides sp’1 .

Note that the two sequences sj and Vj are connected by the relation sj =

j’1

V2j /22 . This form of the Lucas-Lehmer test is easier to compute, since the calcu-

lation of sp’1 (mod Mp ) only involves p’2 squarings modulo the Mersenne number

Mp . Note that in this case the modular reduction can be done with a single addi-

tion because of the special form of the Mersenne number. Thus the computational

complexity of the Lucas-Lehmer test is O(log2 (Mp )) squarings.

Therefore it is fair to say that the test of Theorem 4.4.5 is about as e¬cient as

the Lucas-Lehmer test for the Mersenne primes. An actual implementation of this

4.5 The Wagsta¬ conjecture 45

test has revealed that Gauss-Mersenne primes exist. The number GMe is a prime

for each e in the set

{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, 27529, 49207, 77291, 85237}.

While we were looking for larger e, M. Oakes et al. [Oak00] found that GMe

is prime for e ∈ {106693, 160423, 203789, 364289} as well. It was shown by us that

this list is complete for e ¤ 188369. Also, no prime number GMe was found with e

in the closed interval [566000, 695566].

Now consider the Eisenstein-Mersenne numbers:

Theorem 4.4.7 The number EMe is a prime if and only if either 2(EMe ’1)/3 ≡

’3e (mod EMe ) or 2(EMe ’1)/3 ≡ 3e ’ 1 (mod EMe ).

Proof: The “if”-part follows directly from Pocklington™s theorem. To show the

“only if”-part, suppose that EMe is a prime. Note that in this case the solutions of

the equation x3 ≡ 1 (mod EMe ) are given by 1, ’3e , and 3e ’1. Hence all that√

needs