Innumber theory, aprime numberp is aSophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called asafe 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 inpublic key cryptography andprimality testing. It has beenconjectured that there areinfinitely many Sophie Germain primes, but this remains unproven.
Sophie Germain primes are named after French mathematicianSophie Germain, who used them in her investigations ofFermat's Last Theorem.[1] One attempt by Germain to prove Fermat’s Last Theorem was to letp be a prime number of the form 8k + 7 and to letn =p – 1. In this case, is unsolvable. Germain’s proof, however, remained unfinished.[2][3] Through her attempts to solve Fermat's Last Theorem, Germain developed a result now known as Germain's Theorem which states that ifp is an odd prime and 2p + 1 is also prime, thenp must dividex,y, orz. Otherwise,. This case wherep does not dividex,y, orz is called the first case. Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time.[2] Later work byKummer and others always divided the problem into first and second cases.
The first few Sophie Germain primes (those less than 1000) are
Hence, the first few safe primes are
Incryptography much larger Sophie Germain primes like 1,846,389,521,368 + 11600 are required.
Two distributed computing projects,PrimeGrid andTwin Prime Search, include searches for large Sophie Germain primes. Some of the largest known Sophie Germain primes are given in the following table.[4]
| Value | Number of digits | Time of discovery | Discoverer |
|---|---|---|---|
| 2618163402417 × 21290000 − 1 | 388342 | February 2016 | Dr. James Scott Brown in a distributedPrimeGrid search using the programs TwinGen andLLR[5] |
| 18543637900515 × 2666667 − 1 | 200701 | April 2012 | Philipp Bliedung in a distributedPrimeGrid search using the programs TwinGen andLLR[6] |
| 183027 × 2265440 − 1 | 79911 | March 2010 | Tom Wu using LLR[7] |
| 648621027630345 × 2253824 − 1 and 620366307356565 × 2253824 − 1 | 76424 | November 2009 | Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza and Antal Járai[8][9] |
| 1068669447 × 2211088 − 1 | 63553 | May 2020 | Michael Kwok[10] |
| 99064503957 × 2200008 − 1 | 60220 | April 2016 | S. Urushihata[11] |
| 607095 × 2176311 − 1 | 53081 | September 2009 | Tom Wu[12] |
| 48047305725 × 2172403 − 1 | 51910 | January 2007 | David Underbakke using TwinGen and LLR[13] |
| 137211941292195 × 2171960 − 1 | 51780 | May 2006 | Járai et al.[14] |
On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of adiscrete logarithm modulo the 240-digit (795 bit) prime RSA-240 + 49204 (the first safe prime above RSA-240) using anumber field sieve algorithm; seeDiscrete logarithm records.
There is no special primality test for safe primes the way there is forFermat primes andMersenne primes. However,Pocklington's criterion can be used to prove the primality of 2p + 1 once one has proven the primality ofp.
Just as every term except the last one of aCunningham 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 isdivisible by 5.
For a safe prime, everyquadratic nonresidue, except -1 (if nonresidue[a]), is aprimitive root. It follows that for a safe prime, the least positive primitive root is a prime number.[15]
With the exception of 7, a safe primeq is of the form 6k − 1 or, equivalently,q ≡ 5 (mod 6) – as isp > 3. Similarly, with the exception of 5, a safe primeq is of the form 4k − 1 or, equivalently,q ≡ 3 (mod 4) — trivially true since (q − 1) / 2 must evaluate to anoddnatural number. Combining both forms usinglcm(6, 4) we determine that a safe primeq > 7 also must be of the form 12k − 1 or, equivalently,q ≡ 11 (mod 12).
It follows that, for any safe primeq > 7:
Ifp is a Sophie Germain prime greater than 3, thenp 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.[16] 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.[17]
If a Sophie Germain primep iscongruent to 3 (mod 4) (OEIS: A002515,Lucasian primes), then its matching safe prime 2p + 1 (congruent to 7 modulo 8) will be a divisor of theMersenne number 2p − 1. Historically, this result ofLeonhard Euler was the first known criterion for a Mersenne number with a prime index to becomposite.[18] It can be used to generate the largest Mersenne numbers (with prime indices) that are known to be composite.[19]
It isconjectured that there are infinitely many Sophie Germain primes, but this has not beenproven.[17] Several other famous conjectures in number theory generalize this and thetwin prime conjecture; they include theDickson's conjecture,Schinzel's hypothesis H, and theBateman–Horn conjecture.
Aheuristic estimate for thenumber of Sophie Germain primes less thann is[17]
where
isHardy–Littlewood's twin prime constant. Forn = 104, this estimate predicts 156 Sophie Germain primes, which has a 20% error compared to the exact value of 190. Forn = 107, the estimate predicts 50822, which is still 10% off from the exact value of 56032. The form of this estimate is due toG. H. Hardy andJ. E. Littlewood, who applied a similar estimate totwin primes.[20]
Asequence (p, 2p + 1, 2(2p + 1) + 1, ...) in which all of the numbers are prime is called aCunningham chain of the first kind. Every term of such a sequence except the last is a Sophie Germain prime, and every term except the first is a safe prime. Extending the conjecture that there exist infinitely many Sophie Germain primes, it has also been conjectured that arbitrarily long Cunningham chains exist,[21] although infinite chains are known to be impossible.[22]
A prime numberq is astrong prime ifq + 1 andq − 1 both have some large (around 500 digits) prime factors. For a safe primeq = 2p + 1, the numberq − 1 naturally has a large prime factor, namelyp, and so a safe primeq meets part of the criteria for being a strong prime. The running times of some methods offactoring a number withq as a prime factor depend partly on the size of the prime factors ofq − 1. This is true, for instance, of thep − 1 method.
Safe primes are also important in cryptography because of their use indiscrete logarithm-based techniques likeDiffie–Hellman key exchange. If2p + 1 is a safe prime, the multiplicativegroup of integersmodulo2p + 1 has asubgroup of large primeorder. 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 top.
A prime numberp = 2q + 1 is called asafe prime ifq is prime. Thus,p = 2q + 1 is a safe prime if and only ifq is a Sophie Germain prime, so finding safe primes and finding Sophie Germain primes are equivalent in computational difficulty. The notion of a safe prime can be strengthened to a strong prime, for which bothp − 1 andp + 1 have large prime factors. Safe and strong primes were useful as the factors of secret keys in theRSA cryptosystem, because they prevent the system being broken by somefactorization algorithms such asPollard'sp − 1 algorithm. However, with the current factorization technology, the advantage of using safe and strong primes appears to be negligible.[23]
Similar issues apply in other cryptosystems as well, includingDiffie–Hellman key exchange and similar systems that depend on the security of thediscrete logarithm problem rather than on integer factorization.[24] For this reason, key generation protocols for these methods often rely on efficient algorithms for generating strong primes, which in turn rely on the conjecture that these primes have a sufficiently high density.[25]
InSophie Germain Counter Mode, it was proposed to use the arithmetic in thefinite field of order equal to the safe prime 2128 + 12451, to counter weaknesses inGalois/Counter Mode using the binary finite field GF(2128). However, SGCM has been shown to be vulnerable to many of the same cryptographic attacks as GCM.[26]
In the first version of theAKS primality test paper, a conjecture about Sophie Germain primes is used to lower the worst-case complexity fromO(log12n) toO(log6n). A later version of the paper is shown to have time complexityO(log7.5n) which can also be lowered toO(log6n) using the conjecture.[27] Later variants of AKS have been proven to have complexity ofO(log6n) without any conjectures or use of Sophie Germain primes.
Safe primes obeying certain congruences can be used to generatepseudo-random numbers of use inMonte Carlo simulation.
Similarly, Sophie Germain primes may be used in the generation ofpseudo-random numbers. The decimal expansion of 1/q will produce astream ofq − 1 pseudo-random digits, ifq is the safe prime of a Sophie Germain primep, withpcongruent to 3, 9, or 11 modulo 20.[28] Thus "suitable" prime numbersq are 7, 23, 47, 59, 167, 179, etc. (OEIS: A000353) (corresponding top = 3, 11, 23, 29, 83, 89, etc.) (OEIS: A000355). The result is a stream oflengthq − 1 digits (including leading zeros). So, for example, usingq = 23 generates the pseudo-random digits 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3. Note that these digits are not appropriate for cryptographic purposes, as the value of each can be derived from its predecessor in the digit-stream.[citation needed]
Sophie Germain primes are mentioned in the stage playProof[29] and thesubsequent film.[30]
If the strong primek-tuples conjecture is true, then Cunningham chains can reach any length.
[Jean E.] Taylor pointed out that the example of a Germain prime given in the preliminary text was missing the term "+ 1." "When I first went to see 'Proof' and that moment came up in the play, I was happy to hear the 'plus one' clearly spoken," Taylor says.
There are a couple of breaks from realism inProof where characters speak in a way that is for the benefit of the audience rather than the way mathematicians would actually talk among themselves. When Hal (Harold) remembers what a Germain prime is, he speaks to Catherine in a way that would be patronizing to another mathematician.