Sophie Germain's prime number

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 number is called a safe prime number. For example, 11 is a prime of Sophie Germain and 2 × 11 + 1 = 23 is her associated sure prime. Sophie Germain primes are named after the French mathematician Sophie Germain (1776-1831), who used them in her investigations of Fermat's Last Theorem. Sophie Germain primes and secure primes have applications in cryptography asymmetric and in primality tests. It has been conjectured that there are infinitely many primes of Sophie Germain, but it remains unproven.

Individual numbers

The first prime numbers of Sophie Germain (those less than 1000) are

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 683, 719, 743, 761, 809, 911, 953,... A005384

Therefore, safe first 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,... A005385

In cryptography much larger Sophie Germain primes like 1,846,389,521,368 + 11⁶⁰⁰ are required.

Two distributed computing projects, PrimeGrid and Twin Prime Search, include large prime number searches by Sophie Germain. Some of the largest known Sophie Germain cousins are given in the table below.

On December 2, 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the calculation of a modulo 240-digit (795-bit) prime discrete logarithm RSA-240+ 49204 (previous first secure prime number was RSA-240) using a general number field screening algorithm; see records in discrete logarithms.

Properties

There is no special primality test for safe primes like there is for Fermat numbers and Mersenne primes. However, the Pocklington criterion can be used to prove the primality of 2p + 1 once the primality of p has been proven.

Just as all terms except the last in a Cunningham chain of the first kind are Sophie Germain primes, so all terms except the first in such a chain are safe primes. Safe primes ending in 7, that is, of the form 10n + 7, are the last terms of such strings when they occur, since 2(10n + 7) + 1 = 20n + 15 is divisible by 5.

If a safe prime q is congruent to 7 modulo 8, then it is a divisor of a Mersenne prime with its corresponding Sophie Germain prime as an exponent.

If q > 7 is a safe prime, so q divides 3^(q−1)/2 - 1. This follows from the fact that 3 is a quadratic residue mod q.

Modular Constraints

With the exception of 7, a safe prime q has the form 6k − 1 or, equivalently, q ≡ 5 (module 6) as p > 3. Similarly, with the exception of 5, a safe prime q has the form 4k + 1 or, equivalently, q ≡ 3 (mod 4), a trivially true fact since (q − 1) / 2 must evaluate to an odd natural number. Combining both forms using lcm(6, 4) it is determined that a safe prime q > 7 must also be of the form 12k - 1 or, equivalently, q ≡ 11 (mod 12). It follows that 3 (also 12) is a quadratic residue modulo q for any safe prime q > 7. (Thus, 12 is not a primitive root of any safe prime q > 7, and the only safe primes that are also long primes in duodecimal are 5 and 7.)

If p is a prime of Sophie Germain greater than 3, then p must be congruent to 2 mod 3. Otherwise, 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 apply for larger prime moduli and are the basis for the choice of the "correction factor" 3. 4; 2C in Sophie Germain's Hardy-Littlewood estimate of the density of prime numbers.

If a prime of Sophie Germain p is congruent to 3 (mod 4) ((sequence A002515 in OEIS), Lucasian primes), then its coincident safe prime 2 p + 1 will be a divisor of the Mersenne prime 2^p - 1. Historically, this result by Leonhard Euler was the first known criterion for a Mersenne number with a prime index outside composite. Can be used to generate the largest Mersenne numbers (with prime indices) known to be composite.

Infinity and density

Unresolved problems of mathematics: Are there infinite prime numbers of Sophie Germain?

It has been conjectured that there are infinitely many Sophie Germain primes, but this proposition has not yet been proven. Several other famous conjectures in number theory generalize this question and the twin primes conjecture, such as the Dickson conjecture, Schinzel's H hypothesis and the Bateman-Horn conjecture.

A heuristic estimate for the number of Sophie Germain's primes less than n is

2Cn(ln n)2≈ ≈ 1.32032n(ln n)2{displaystyle 2C{frac {n}{(ln n)}}}}{approx 1.32032{frac {n}{(ln n)^{2}}}}}}}}}}

where

2}{frac {p(p-2)}{(p-1)^{2}}}{text{aprox. }}0.660161}" xmlns="http://www.w3.org/1998/Math/MathML">C= p▪2p(p− − 2)(p− − 1)2approx.0.660161{displaystyle C=prod _{p HCFC2}{frac {p(p-2)}{(p-1)^{2}}{text{aprox. }0.661}2}{frac {p(p-2)}{(p-1)^{2}}}{text{aprox. }}0.660161}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/caf1f8ed91613dac02d4a785d70317927932e99a" style="vertical-align: -3.338ex; width:32.977ex; height:7.176ex;"/>

is the constant twin cousin of Hardy-Littlewood. For n = 10⁴, this estimate predicts 156 Sophie Germain primes, which is 20% in error compared to the exact value of 190. For n = 10⁷, the estimate predicts 50822, which is still 10% short of the exact value of 56032. The shape of this estimate is due to Godfrey Harold Hardy and John Edensor Littlewood, who applied a similar estimate to twin primes.

A sequence (p, 2p + 1, 2(2p + 1) + 1,...) in the that all numbers are prime is called a Cunningham chain of the first class. Every term in such a sequence except the last one is a Sophie Germain prime, and every term except the first one is a sure prime. Extending Sophie Germain's conjecture that infinitely many primes exist, it has also been conjectured that arbitrarily long Cunningham chains exist, although infinite chains are known to be impossible.

Strong cousins

A prime number q is a strong prime if both q + 1 and q − 1 have some large prime factors (about 500 digits). For a safe prime q= 2p + 1, the number q − 1 naturally has a large prime factor, namely p, so a safe prime q meets part of the criteria for being a strong cousin. The execution times of some methods of factoring a number with q as a prime factor depend in part on the size of the prime factors of q − 1. This is true, for example, for the method p − 1.

Applications

Cryptography

Secure primes are also important in cryptography due to their use in discrete logarithm-based techniques such as Diffie-Hellman rekeying. If 2p + 1 is a safe prime, then the multiplicative group of the integers modulo 2p + 1 has a subgroup of large prime order. In general, this subgroup of prime order is desirable, and the reason for using safe primes is to keep the modulus as small as possible relative to p.

A prime number p = 2q + 1 is called sure prime if q is prime. Therefore, p = 2q + 1 is a safe prime if and only if q is a prime of Sophie Germain, so finding safe primes and finding Sophie Germain's primes are equivalent in computational difficulty. The notion of a strong prime can be reinforced to a strong prime, for which both p − 1 and p + 1 have large prime factors. Safe and strong primes were useful as factors of secret keys in the RSA cryptographic system, because they prevent the system from being broken by some factorization algorithms such as Pollard's p − 1 algorithm. However, with current factorization technology, the advantage of using strong and safe primes appears to be negligible.

Similar problems also apply in other cryptosystems, including the Diffie-Hellman rekeying system and similar systems that rely on discrete logarithm security rather than integer factorization. For this reason, protocols Key generation methods for these methods are often based on efficient algorithms for generating strong primes, which in turn are based on the conjecture that these primes have a sufficiently high density.

In Sophie Germain's Counter Mode it was proposed to use arithmetic on the finite field of order equal to Sophie Germain's prime number 2¹²⁸ + 12451, to counteract the weaknesses of the Galois/Counter Mode using the finite binary field GF(2¹²⁸). However, SGCM has been shown to be vulnerable to many of the same cryptographic attacks as GCM.

Primality test

In the first version of the AKS Primality Test paper, a Sophie Germain conjecture on primes was used to reduce the complexity of the worst-case O(log¹²n) to O(log⁶n). A later version of the document is shown to have a time complexity O(log^7.5n) which can also be reduced to O(log⁶n) using the conjecture. Later variants of the AKS Test have been shown to have a complexity of O(log⁶n) without guesswork and use of Sophie Germain primes.

Generation of pseudorandom numbers

Safe primes that obey certain congruences can be used to generate pseudorandom numbers for use in the Monte Carlo method.

Similarly, Sophie Germain's primes can be used in the generation of pseudorandom numbers. The decimal expansion of 1/q will produce a stream of q − 1 pseudorandom digits, if q is the safe prime of a Sophie Germain prime p, with p congruent to 3, 9, or 11 modulo 20. Thus, "proper" q is 7, 23, 47, 59, 167, 179, etc. ((sequence A000353 in OEIS)) (corresponding to p = 3, 11, 23, 29, 83, 89, etc.) ((sequence A000355 in OEIS)). The result is a sequence of length q − 1 digits (including leading zeros). So, for example, using q= 23 generates the pseudorandom 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 suitable for cryptographic purposes, since the value of each can be deduced from its predecessor in the digit stream.

In popular culture

Sophie Germain's cousins are mentioned in the play The Test and the film of the same name.