Safe prime

A safe prime is a prime number of the form 2p + 1, where p is also a prime. (Conversely, the prime p is a Sophie Germain prime.) The first few safe primes are

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907

These primes are called "safe" because of their application in encryption algorithms such as Diffie-Hellman. It should of course be noted that no prime less than about 10⁵⁰ is really secure since any modern computer with a suitable algorithm can determine their primality in a reasonable period of time. But the small safe primes are still useful for teaching the principles of the system. There is no special primality test for safe primes the way there is for Fermat primes and Mersenne primes.

With the exception of 5, there are no Fermat primes that are also safe primes. A little reflection will show that given a Fermat prime F, it will turn out that (F - 1)/2 is a power of two.

With the exception of 7, there are no Mersenne primes that are also safe primes. The proof of this is a little more involved, but still within the realm of basic algebra. Accepting as true that p must be prime for 2^p - 1 to have a chance to be prime also, it follows that ((2^p - 1) - 1)/2 = 2^{p - 1} - 1, that is, a Mersenne number. But p - 1 is never prime, with the exception of p = 3, corresponding neatly with 2³ - 1 = 7.

Just as every term except the last one of a Cunningham chain of the first kind is a Sophie Germain prime, so every term except the first of such a chain is a safe prime. Safe primes ending in 7, that is, of the form 10n + 7, are the last terms in such chains when they occur, since 2(10n + 7) + 1 = 20n + 15.