« AFB
Star height problem »
Apr
29

Safe prime

posted by admin in , , , Uncategorized

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.

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. 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 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 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.

There is no special primality test for safe primes the way there is for Fermat primes and Mersenne primes. However, Pocklington’s criterion can be used to prove the primality of 2p+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 2p−1 to have a chance to be prime also, it follows that ((2p−1)−1)/2 = 2p−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 10n+7, are the last terms in such chains when they occur, since 2(10n+7) + 1 = 20n+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.

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. [1]

On June 18, 2005, Antoine Joux and Reynald Lercier announced that they computed a discrete logarithm modulo a 130-digit safe prime. [2]


External link

  • Safe prime at planetmath.org

Did you enjoy Safe prime? Subscribe to RSS Feed.

Social Bookmarking
Add to: Digg Add to: Del.icio.us Add to: Technorati Add to: StumbleUpon Add to: Reddit Add to: Slashdot Add to: Netscape Add to: Furl Add to: Newsvine Add to: Yahoo Add to: Google Add to: Blinklist Add to: Spurl Add to: Diigo Add to: Ma.Gnolia

Do you have something to say? Say it below.

You must be logged in to post a comment.