In

number theory, a

prime number *p* is a

**Sophie
Germain prime** if 2

*p* + 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
6

*k*−1 or, equivalently,

*p* ≡ 5 (mod 6) — as is its
matching

safe prime 2

*p*+1. We
note that the other form for a prime

*p* > 3 is
6

*k*+1 or, equivalently,

*p* ≡ 1 (mod 6), and that
3|(2

*p*+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:

- 2, 3,
5, 11,
23, 29,
41, 53,
83, 89,
113, 131,
173, 179,
191, 233,
…... .

The largest known Sophie Germain primes are 648621027630345 ×
2

^{253824}−1 and 620366307356565 × 2

^{253824}−1.
They both have 76424 decimal digits and were found in November 2009
by Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza and Antal
Járai. The previous record was set 6 weeks earlier, 607095 ×
2

^{176311}−1 with 53081 digits, found by Tom Wu using the
program LLR.Before that the record was 48047305725 ×
2

^{172403}−1 with 51910 digits, found by David Underbakke
in January 2007 using the programs TwinGen and LLR. And before
that, the record was held by the same team as the November 2009
records, 137211941292195 × 2

^{171960}−1 with 51780 digits,
found in May 2006.

A

heuristic estimate (due to

G. H. Hardy and

J.
E. Littlewood) for the

number of Sophie Germain primes less than

*n*
is 2

*C*_{2} *n* / (

ln *n*)

^{2} where

*C*_{2} is the

twin
prime constant, approximately 0.660161. For

*n* =
10

^{4}, this estimate predicts 156 Sophie Germain primes,
which has a 20% error compared to the exact value of 190. For

*n* = 10

^{7}, the estimate predicts 50822,
which is still 10% off from the exact value of 56032.

A sequence {

*p*, 2

*p* + 1,
2(2

*p* + 1) + 1, ...} of 1 or more
Sophie Germain primes, ending with a prime which does not have to
be a Sophie Germain, 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 2

*p*+1 will be a divisor of the

Mersenne number
2

^{p}−1.

Sophie Germain primes were mentioned in the stage play

*Proof* and the

subsequent film.

## Application in (pseudo-)random number generation

Sophie Germain primes have a practical application 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). 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); for more see

OEIS sequence . 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.

## References

## Further reading

## External links