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 In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... A prime number p is called a Sophie Germain prime if 2p + 1 is also prime. ...

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) Look up five in Wiktionary, the free dictionary. ... Seven Days of Creation - 1765 book, title page 7 (seven) is the natural number following 6 and preceding 8. ... 11 (eleven) is the natural number following 10 and preceding 12. ... 23 (twenty-three) is the natural number following 22 and preceding 24. ... 47 (forty-seven) is the natural number following 46 and preceding 48. ... 59 (fifty-nine) is the natural number following 58 and preceding 60. ... 83 (eighty-three) is the natural number following 82 and preceding 84. ... 107 is the natural number following 106 and preceding 108. ... 167 is the natural number following 166 and preceding 168. ... 179 is the natural number between 178 and 180. ... 227 is the natural number between 226 and 228. ... 263 is the natural number between 262 and 264. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

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). The word modulo (Latin, with respect to a modulus of ___) is the Latin ablative of modulus which itself means a small measure. ... A prime number p is called a Sophie Germain prime if 2p + 1 is also prime. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ...

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. A strong prime is a type of prime number that is sometimes used for certain cryptographic applications such as key generation for RSA keys. ... Prime decomposition redirects here. ... Pollards rho algorithm is a special-purpose integer factorization algorithm. ... This article is about an algorithm for public-key encryption. ...

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. In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. ... Diffie-Hellman (D-H) key exchange is a cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. ... This picture illustrates how the hours on a clock form a group under modular addition. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In group theory, the term order is used in two closely related senses: the order of a group is its cardinality, i. ...

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. In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form where n is a nonnegative integer. ... In mathematics, a Mersenne number is a number that is one less than a power of two. ...

With the exception of 5, there are no Fermat primes that are also safe primes. Since Fermat primes are of the form F=2ⁿ+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 6k-1. Mersenne primes are of the form 2^m-1, but 2^m-1=6k-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 10n+7, are the last terms in such chains when they occur, since 2(10n+7) + 1 = 20n+15 is divisible by 5. In mathematics, a Cunningham chain is a certain sequence of prime numbers. ...

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. In mathematics, a Mersenne prime is a prime number that is one less than a power of two. ... A prime number p is called a Sophie Germain prime if 2p + 1 is also prime. ...

As of January 2007, the largest known safe prime is 48047305725·2¹⁷²⁴⁰⁴−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] 2007 is a common year starting on Monday of the Gregorian calendar. ... is the 25th day of the year in the Gregorian calendar. ... Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era in the 21st century. ...

On June 18, 2005, Antoine Joux and Reynald Lercier announced that they computed a discrete logarithm modulo a 130-digit safe prime. [2] is the 169th day of the year (170th in leap years) in the Gregorian calendar. ... Year 2005 (MMV) was a common year starting on Saturday (link displays full calendar) of the Gregorian calendar. ... In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. ...

External link

• Safe prime at planetmath.org