| Safe Prime |
Article Index for Safe |
Website Links For Safe |
Information AboutSafe Prime |
| CATEGORIES ABOUT SAFE PRIME | |
| prime numbers | |
| cryptography | |
|
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 relationship to standard mandates that strong primes be used for RSA moduli. Safe primes are also important in cryptography because of their use in Discrete Logarithm -based techniques like Diffie-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 and Mersenne 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. 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 23 - 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 10''n'' + 7, are the last terms in such chains when they occur, since 2(10''n'' + 7) + 1 = 20''n'' + 15. 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. On June 18, 2005, Antoine Joux and Reynald Lercier have announced that they computed a Discrete Logarithm modulo a 130 digit safe prime. |
|
|