In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven. Sophie Germain primes are named after the French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. One attempt by Germain to prove Fermat's Last Theorem was to let p be a prime number of the form 8k + 7 and to let n = p – 1. In this case, x n + y n = z n {\displaystyle x^{n}+y^{n}=z^{n}} is unsolvable. Germain's proof, however, remained unfinished. Through her attempts to solve Fermat's Last Theorem, she proved a result now known as Sophie Germain's theorem, which states that if p is an odd prime and 2p + 1 is also prime, then p must divide x, y, or z. Otherwise, x n + y n ≠ z n {\textstyle x^{n}+y^{n}\neq z^{n}} . This case where p does not divide x, y, or z is called the first case. Sophie Germain's work was the most progress achieved on Fermat's last theorem at that time. Later work by Kummer and others always divided the problem into first and second cases.
Individual numbers The first few Sophie Germain primes (those less than 1000) are
2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, ... OEIS: A005384 Hence, 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, ... OEIS: A005385 In cryptography, much larger Sophie Germain primes like 1,846,389,521,368 + 11600 are required. Two distributed computing projects, PrimeGrid and Twin Prime Search, include searches for large Sophie Germain primes. Some of the largest known Sophie Germain primes are given in the following table.
On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a discrete logarithm modulo the 240-digit (795 bit) prime RSA-240 + 49204 (the first safe prime above RSA-240) using a number field sieve algorithm; see Discrete logarithm records.
Properties 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. 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. For a safe prime, every quadratic nonresidue, except −1 (if nonresidue), is a primitive root. It follows that for a safe prime, the least positive primitive root is a prime number.
Modular restrictions 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. 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). It follows that, for any safe prime q > 7:
both 3 and 12 are quadratic residues mod q (per law of quadratic reciprocity) neither 3 nor 12 is a primitive root of q the only safe primes that are also full reptend primes in base 12 are 5 and 7 q divides 3(q−1)/2 − 1 and 12(q−1)/2 − 1, same as 3(q−1)/2 ≡ 1 mod q and 12(q−1)/2 ≡ 1 mod q (per Euler's criterion) q − 3, q − 4, q − 9, q − 12 are quadratic nonresidues q − 3, q − 4, q − 9, and, for q > 11, q − 12 are primitive roots If p is a Sophie Germain prime greater than 3, then p must be congruent to 2 mod 3. For, if not, it would be congruent to 1 mod 3 and 2p + 1 would be congruent to 3 mod 3, impossible for a prime number. Similar restrictions hold for larger prime moduli, and are the basis for the choice of the "correction factor" 2C in the Hardy–Littlewood estimate on the density of the Sophie Germain primes. If a Sophie Germain prime p is congruent to 3 (mod 4) ((sequence A002515 in the OEIS), Lucasian primes), then its matching safe prime 2p + 1 (congruent to 7 modulo 8) will be a divisor of the Mersenne number 2p − 1. Historically, this result of Leonhard Euler was the first known criterion for a Mersenne number with a prime index to be composite. It can be used to generate the largest Mersenne numbers (with prime indices) that are known to be composite.
Infinitude and density
It is conjectured that there are infinitely many Sophie Germain primes, but this has not been proven. Several other famous conjectures in number theory generalize this and the twin prime conjecture; they include Dickson's conjecture, Schinzel's hypothesis H, and the Bateman–Horn conjecture. A heuristic estimate for the number of Sophie Germain primes less than n is
… excerpt ends here. Continue reading the full article.
