Sophie Germain prime
Encyclopedia : S : SO : SOP : Sophie Germain prime
A prime number p is called a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, also prime. These numbers are named after French mathematician Marie-Sophie Germain.
A Sophie Germain Prime p > 3 is of the form 6k - 1 or, equivalently, p ≡ 5 (mod 6). As is its matching safe prime (2p + 1). We note that the other form for a prime p > 3 is 6k + 1 or, equivalently, p ≡ 1 (mod 6), and that 3|(2p + 1) — thus excluding such p from the Sophie Germain Prime domain. This is trivially proven using modular arithmetic.
It is conjectured that there are infinitely many Sophie Germain primes, but like the twin prime conjecture, this has not been proven. The first few Sophie Germain primes are (sequence in OEIS):
Currently, the largest known Sophie Germain prime is 7068555 × 2121301 - 1, discovered by Predrag Minovic in January 2005, using TwinGen and LLR.
A heuristic estimate (due to G. H. Hardy and J. E. Littlewood) for the number of Sophie Germain primes less than n is 2C2 n / (ln n)2 where C2 is the twin prime constant, approximately 0.660161. For n = 104, this estimate predicts 156 Sophie Germain primes, which has a 20% error compared to the exact value of 190 above. For n = 107, the estimate predicts 50822, which is still 10% off from the exact value of 56032.
A sequence of Sophie Germain primes is called a Cunningham chain of the first kind. Every term of such a sequence except the first and last is both a Sophie Germain prime and a safe prime.
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.
Sophie Germain primes were the subject of the eponymous proof in the stage play Proof and the subsequent film Proof.
Application in random number generation
Sophie Germain primes have a practical application in the generation of random numbers. The decimal expansion of reciprocal 1/q will produce a stream of pseudo random numbers of length q - 1 if q is such that q = 2S + 1 where S is a Sophie Germain prime, such that both S and 2S + 1 are prime, with S being of the form 3, 9 or 11 mod 20. Thus “suitable” prime numbers q are 7, 23, 47, 59, 167, 179, etc (corresponding to S = 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 random digits 0,4,3,4,7,8,2,6.....3,9,1,3External references
- [The Ten Largest Known Sophie Germain Primes] from The Prime Pages
- Maximally Periodic Reciprocals R.A.J. Matthews Bulletin of the Institute of Mathematics and its Applications vol 28 pp 147-148 1992
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.