A safe prime is a prime number of the form 2p + 1, where p is also a prime.

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.

Safe primes are important in cryptography because of (among other things) their use in discrete logarithm-based techniques like Diffie-Hellman key exchange. If 2p + 1 is a safe prime, the multiplicative group of numbers modulo 2p + 1 has a subgroup of large prime order. It is usually this prime-order subgroup that is desirable, and the reason for using safe primes is so that the modulus is as small as possible relative to p.

history | show excerpt | excerpt history