#jsDisabledContent { display:none; } My Account | Register | Help

# Sophie Germain prime

Article Id: WHEBN0000089244
Reproduction Date:

 Title: Sophie Germain prime Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Sophie Germain prime

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, 29 is a Sophie Germain prime and 2 × 29 + 1 = 59 is its associated safe prime. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem.[2] 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.

## Individual numbers

The first few Sophie Germain primes are: (less than 1000)

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

In cryptography much larger Sophie Germain primes like 1,846,389,521,368 + 11^{600} are required.

Two distributed computing projects, PrimeGrid and Twin Prime Search, include searches for large Sophie Germain primes.

The largest known Sophie Germain primes as of August 2013 are:[3]
Value Number of digits Time of discovery Discoverer
18543637900515 × 2666667−1 200701 April 2012 Philipp Bliedung in a distributed PrimeGrid search using the programs TwinGen and LLR[4]
183027 × 2265440−1 79911 March 2010 Tom Wu using LLR[5]
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[6][7]
607095 × 2176311−1 53081 September 2009 Tom Wu[8]
48047305725 × 2172403−1 51910 January 2007 David Underbakke using TwinGen and LLR[9]
137211941292195 × 2171960−1 51780 May 2006 Járai et al.[10]

## Infinitude and density

 Open problem in mathematics: Are there infinitely many Sophie Germain primes? (more open problems in mathematics)

It is conjectured that there are infinitely many Sophie Germain primes, but this has not been proven.[11] Several other famous conjectures in number theory generalize this and the twin prime conjecture; they include the 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[11]

2C \frac{n}{(\ln n)^2} \approx 1.32032\frac{n}{(\ln n)^2}

where

C=\prod_{p>2} \frac{p(p-2)}{(p-1)^2}\approx 0.660161

is the twin prime constant. For n = 104, this estimate predicts 156 Sophie Germain primes, which has a 20% error compared to the exact value of 190. For n = 107, the estimate predicts 50822, which is still 10% off from the exact value of 56032. The form of this estimate is due to G. H. Hardy and J. E. Littlewood, who applied a similar estimate to twin primes.[12]

A sequence {p, 2p + 1, 2(2p + 1) + 1, ...} in which all of the numbers are prime is called a Cunningham 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,[13] although infinite chains are known to be impossible.[14]

Another relevant open problem is Rassias' conjecture according to which, for any prime number p>2, there exist two prime numbers p_1, p_2, with p_1 such that (p-1)p_1=p_2+1. We thus see a combination of a generalized Sophie Germain twin problem p_2=2ap_1-1, strengthened by the additional condition that 2a+1 be a prime number too (see [15][16]).

## Modular restrictions

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.[17] 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.[11]

If a Sophie Germain prime p is congruent to 3 (mod 4), then its matching safe prime 2p + 1 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.[18] It can be used to generate the largest Mersenne numbers (with prime indices) that are known to be composite.[19]

## Applications

### Cryptography

A prime number p = 2q + 1 is called a safe prime if q is prime. Thus, p = 2q + 1 is a safe prime if and only if q 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 both p − 1 and p + 1 have large prime factors. Safe and strong primes are useful as the factors of secret keys in the RSA cryptosystem, because they prevent the system being broken by certain factorization algorithms such as Pollard's rho algorithm that would apply to secret keys formed from non-strong primes.[20]

Similar issues apply in other cryptosystems as well, including Diffie-Hellman key exchange and similar systems that depend on the security of the discrete log problem rather than on integer factorization.[21] 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.[22]

In Sophie Germain Counter Mode, it was proposed to use the arithmetic in the finite field of order equal to the Sophie Germain prime 2128 + 12451, to counter weaknesses in Galois/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.[23]

### Primality testing

Sophie Germain primes play an important role in the AKS primality test: if they exist in the conjectured density, then they can be used as the primes over which the algorithm does its modular arithmetic. This would speed up its running time to O(n6) (where n denotes the number of digits of the input number) compared to a version of the algorithm that does not need this assumption and takes time O(n10.5).[24]

### Pseudorandom number generation

Sophie Germain primes may be used in the generation of pseudo-random numbers. The decimal expansion of 1/q will produce a stream of q − 1 pseudo-random digits, if q is the safe prime of a Sophie Germain prime p, with p congruent to 3, 9, or 11 (mod 20).[25] Thus “suitable” prime numbers q are 7, 23, 47, 59, 167, 179, etc. () (corresponding to p =  3, 11, 23, 29, 83, 89, etc.) (). The result is a stream of length q − 1 digits (including leading zeros). So, for example, using q = 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.

## In popular culture

Sophie Germain primes are mentioned in the stage play Proof[26] and the subsequent film.[27]

## References

1. ^
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.