Computer Security and Cryptography

13.10 PERFECT NUMBERS AND THE MERSENNE PRIMES

The integer n is perfect if the sum of all of its divisors is equal to 2n. Mystical interpretations were given to perfect numbers.⁵ The first four perfect numbers are

TABLE 13.14 Mersenne Primes

The perfect numbers listed above are all even; it is not known if odd perfect numbers exist. In the third century B.C., Euclid proved that if p and 2^p − 1 are prime, then 2^{p − 1}(2^p − 1) is perfect. Euler proved in the eighteenth century that every even perfect number was of this form.

Marin Mersenne (1588–1648) was a monk in the Order of Minims near Paris. He taught philosophy and was interested in science and mathematics. If 2ⁿ − 1 (n > 2) is a prime, then n must be a prime; for if N = st, then 2^st − 1 = (2^s − 1) (2^{s(t − 1)} + 2^{s(t − 2)} + · · · + 1). In 1644 Mersenne conjectured that 2^p − 1 is a prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 and these were the only solutions for p ≤ 257. It is unlikely that Mersenne could have tested all of these numbers in 1644 and his conjecture is not completely correct.

Table 13.14 lists 43 known Mersenne numbers, the last discovered on December 15, 2005, by Dr Curtis Cooper and Dr Steven Boone, professors ...