 (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.