(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 2^{s} - 1. If 2^{s} - 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 = 2^{s} - 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 u_{s}_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 (u^{2} - 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 2^{s} —1 is prime.