(True) Primality tests

The primality tests in this section are methods by which positive integers can be proven to be prime, and are often referred to as primality proving algorithms. These primality tests are generally more computationally intensive than the probabilistic primality tests of §4.2. Consequently, before applying one of these tests to a candidate prime n, the candidate should be subjected to a probabilistic primality test such as Miller-Rabin (Algorithm 4.24).

4.34 Definition An integer n which is determined to be prime on the basis of a primality proving algorithm is called a provable prime.

Testing Mersenne numbers

Efficient algorithms are known for testing primality of some special classes of numbers, such as Mersenne numbers and Fermat numbers. Mersenne prunes n are useful because the arithmetic in the field Z„ for such n can be implemented very efficiently (see §14.3.4). The Lucas-Lehmer test for Mersenne numbers (Algorithm 4.37) is such an algorithm.

4.35 Definition Let ,s > 2 be an integer. A Mersenne number is an integer of the form 2s - 1. If 2s - 1 is prime, then it is called a Mersenne prime.

The following are necessary and sufficient conditions for a Mersenne number to be prime.

  • 4.36 Fact Let s > 3. The Mersenne number n = 2s - 1 is prime if and only if the following two conditions are satisfied:
    • (i) s is prime; and
    • (ii) the sequence of integers defined by щ = 4 and u^+i = (u - 2) mod n for к > 0 satisfies us_2 = 0.

Fact 4.36 leads to the following deterministic polynomial-time algorithm for determining (with certainty) whether a Mersenne number is prime.

4.37 Algorithm Lucas-Lehmer primality test for Mersenne numbers

INPUT: a Mersenne number n = 2,s - 1 with s > 3.

OUTPUT: an answer “prime” or “composite” to the question: “Is n prune?”

  • 1. Use trial division to check if s has any factors between 2 and |_/SJ. If it does, then return(“composite”).
  • 2. Setut-4.
  • 3. For к from 1 to s - 2 do the following: compute (u2 - 2) mod n.
  • 4. If и = 0 then retum(“prime”). Otherwise, retum(“composite”).

It is unknown whether there are infinitely many Mersenne primes. Table 4.2 lists the 33 known Mersenne primes.

Index

j

Mj

decimal

digits

1

2

1

2

3

1

3

5

2

4

7

3

5

13

4

6

17

6

7

19

6

8

31

10

9

61

19

10

89

27

11

107

33

12

127

39

13

521

157

14

607

183

15

1279

386

1G

2203

664

17

2281

687

Index

j

Mj

decimal

digits

18

3217

969

19

4253

1281

20

4423

1332

21

9689

2917

22

9941

2993

23

11213

3376

24

19937

6002

25

21701

6533

26

23209

6987

27

44497

13395

28

86243

25962

29

110503

33265

30

132049

39751

31

216091

65050

32?

756839

227832

33?

859433

258716

Table 4.2: Known Mersenne primes. The table shows the 33 biown exponents Mj, 1 < j < 33, for which 2м* — 1 is a Mersenne prime, and also the number of decimal digits in 2м* — 1. The question marks after j = 32 and j = 33 indicate that it is not known whether there are any other exponents s between M31 and these numbers for which 2s —1 is prime.

 
Source
< Prev   CONTENTS   Source   Next >