- Safe prime
A safe prime is a
prime number of the form 2"p" + 1, where "p" is also a prime. (Conversely, the prime "p" is aSophie Germain prime .) The first few safe primes are5, 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. OEIS|id=A005385
With the exception of 7, a safe prime "q" is of the form 6"k"−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 4"k"−1 or, equivalently, "q" ≡ 3 (mod 4) — trivially true since ("q"−1) / 2 must evaluate to an oddnatural number . Combining both forms using lcm(6,4) we determine that a safe prime "q" > 7 also must be of the form 12"k"−1 or, equivalently, "q" ≡ 11 (mod 12).These primes are called "safe" because of their relationship to
strong prime s. A prime number "q" is a "strong" prime if "q"+1 and "q"−1 both have large prime factors. 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, theANSI X9.31 standard mandates that strong primes be used forRSA moduli.Safe primes are also important in cryptography because of their use in
discrete logarithm -based techniques likeDiffie-Hellman key exchange . If 2"p"+1 is a safe prime, the multiplicative group of numbers modulo 2"p"+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".There is no special primality test for safe primes the way there is for
Fermat prime s andMersenne prime s. However, Pocklington's criterion can be used to prove the primality of 2"p"+1 once one has proven the primality of "p".With the exception of 5, there are no Fermat primes that are also safe primes. Since Fermat primes are of the form "F"=2n+1, it follows that ("F"−1)/2 is a
power of two .With the exception of 7, there are no Mersenne primes that are also safe primes. This follows from the statement above that all safe primes except 7 are of the form 6"k"-1. Mersenne primes are of the form 2"m"-1, but 2"m"-1=6"k"-1 would imply that 2"m" is divisible by 6, which is impossible.
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 10"n"+7, are the last terms in such chains when they occur, since 2(10"n"+7) + 1 = 20"n"+15 is divisible by 5.If a safe prime "q" is congruent to 7 mod 8, then it is a divisor of the
Mersenne number with its matching Sophie Germain prime as exponent.As of January 2007, the largest known safe prime is 48047305725·2172404−1. This prime, along with the corresponding largest known Sophie Germain prime, were found by David Underbakke on
January 25 ,2007 using the programs TwinGen and LLR. [http://primes.utm.edu/primes/page.php?id=79261]On
June 18 ,2005 , Antoine Joux and Reynald Lercier announced that they computed adiscrete logarithm modulo a 130-digit safe prime. [http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0506&L=nmbrthry&T=0&P=2037]References
*
M. Abramowitz andI. A. Stegun , eds., "Handbook of Mathematical Functions", National Bureau of Standards, Applied Math. Series 55, Tenth Printing, (1972): 870External links
* [http://planetmath.org/encyclopedia/SafePrime.html Safe prime] at planetmath.org
Wikimedia Foundation. 2010.