- published: 25 Mar 2015
- views: 17190
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. (sequence A005385 in OEIS)
With the exception of 7, a safe prime q is of the form 6k − 1 or, equivalently, q ≡ 5 (mod 6) — as is p > 3 (c.f. Sophie Germain prime, second paragraph). Similarly, with the exception of 5, a safe prime q is of the form 4k − 1 or, equivalently, q ≡ 3 (mod 4) — trivially true since (q − 1) / 2 must evaluate to an odd natural number. Combining both forms using lcm(6,4) we determine that a safe prime q > 7 also must be of the form 12k−1 or, equivalently, q ≡ 11 (mod 12).
These primes are called "safe" because of their relationship to strong primes. A prime number q is a strong prime if q + 1 and q − 1 both have large prime factors. For a safe prime q = 2p + 1, the number q − 1 naturally has a large prime factor, namely p, and so safe prime q meets part of the criteria for being a strong prime. The running times of some methods of factoring a number with q as a prime factor depend partly on the size of the prime factors of q − 1. This is true, for instance, of the Pollard rho +1 and −1 methods. Although the most efficient known integer factorization methods do not depend on the size of the prime factors of q−1, this is nonetheless considered important in cryptography: for instance, the ANSI X9.31 standard mandates that strong primes (not safe primes) be used for RSA moduli.