Sophie Germain prime
Encyclopedia
In number theory
, a prime number
p is 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, and 47 is also a prime number. 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 conjecture
d that there are infinitely many Sophie Germain primes, but this has not been proven
.
The first few Sophie Germain primes are:
The largest known Sophie Germain prime is 183027 × 2265440−1. It has 79911 decimal digits and was found in March 2010 by Tom Wu using the program LLR. Before that the two largest were 648621027630345 × 2253824−1 and 620366307356565 × 2253824−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 × 2176311−1 with 53081 digits, found by Tom Wu.
Before that the record was 48047305725 × 2172403−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 × 2171960−1 with 51780 digits, found in May 2006. the above are still the six largest known Sophie Germain primes.
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. For n = 107, the estimate predicts 50822, which is still 10% off from the exact value of 56032.
A sequence {p, 2p + 1, 2(2p + 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 2p + 1 will be a divisor of the Mersenne number 2p − 1.
Sophie Germain primes were mentioned in the stage play Proof
and the subsequent film
.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
p is 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, and 47 is also a prime number. These numbers are named after French
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Marie-Sophie Germain
Sophie Germain
Marie-Sophie Germain was a French mathematician, physicist, and philosopher. Despite initial opposition from her parents and difficulties presented by a gender-biased society, she gained education from books in her father's library and from correspondence with famous mathematicians such as...
.
A Sophie Germain prime p > 3 is of the form 6k−1 or, equivalently, p ≡ 5 (mod 6) — as is its matching safe prime
Safe prime
A safe prime is a prime number of the form 2p + 1, where p is also a prime. The first few safe primes are...
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
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
.
It is conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
d that there are infinitely many Sophie Germain primes, but this has not been proven
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
.
The first few Sophie Germain primes are:
- 2, 3, 5, 1111 (number)11 is the natural number following 10 and preceding 12.Eleven is the first number which cannot be counted with a human's eight fingers and two thumbs additively. In English, it is the smallest positive integer requiring three syllables and the largest prime number with a single-morpheme name...
, 2323 (number)23 is the natural number following 22 and preceding 24.- In mathematics :Twenty-three is the ninth prime number, the smallest odd prime that is not a twin prime. Twenty-three is also the fifth factorial prime, the third Woodall prime...
, 2929 (number)29 is the natural number following 28 and preceding 30.-In mathematics:It is the tenth prime number, and also the fourth primorial prime. It forms a twin prime pair with thirty-one, which is also a primorial prime. Twenty-nine is also the sixth Sophie Germain prime. It is also the sum of three...
, 4141 (number)41 is the natural number following 40 and preceding 42.-In mathematics:Forty-one is the 13th smallest prime number. The next is forty-three, with which it comprises a twin prime...
, 5353 (number)53 is the natural number following 52 and preceding 54.-In mathematics:Fifty-three is the 16th prime number. It is also an Eisenstein prime....
, 8383 (number)83 is the natural number following 82 and preceding 84.-In mathematics:Eighty-three is the sum of three consecutive primes as well as the sum of five consecutive primes ....
, 89, 113113 (number)113 is the natural number following 112 and preceding 114.-In mathematics:One hundred [and] thirteen is the 30th prime number, following 109 and preceding 127, a Sophie Germain prime, a Chen prime and a Proth prime as it is a prime number of the form 7 × 24 + 1...
, 131131 (number)131 is the natural number following 130 and preceding 132.-In mathematics:131 is a Sophie Germain prime, the second 3-digit palindromic prime, and also a permutable prime with 113 and 311. It can be expressed as the sum of three consecutive primes, 131 = 41 + 43 + 47. 131 is an Eisenstein prime...
, 173173 (number)173 is the natural number following 172 and preceding 174.-In mathematics:* 173 is an odd number* 173 is a balanced prime* 173 is a deficient number* 173 is an Eisenstein prime with no imaginary part* 173 is an Odious number* 173 is a prime number...
, 179179 (number)179 is the natural number following 178 and preceding 180.-In mathematics:* 179 is an odd number* 179 is a deficient number, as 1 is less than 179* 179 is a Gaussian number* 179 is an odious number* 179 is a square-free number...
, 191191 (number)191 is the natural number following 190 and preceding 192.-In mathematics:* 191 is an odd number* 191 is a centered 19-gonal number* 191 is a deficient number, as 1 is less than 191...
, 233233 (number)233 is the natural number between 232 and 234. It is also a prime number.-In mathematics:233 is an irregular prime, a full reptend prime, a cousin prime, a Chen prime, a Fibonacci prime and a sexy prime. It is the 13th Fibonacci number. It is an Eisenstein prime of the form 3n - 1 with no...
, …... .
The largest known Sophie Germain prime is 183027 × 2265440−1. It has 79911 decimal digits and was found in March 2010 by Tom Wu using the program LLR. Before that the two largest were 648621027630345 × 2253824−1 and 620366307356565 × 2253824−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 × 2176311−1 with 53081 digits, found by Tom Wu.
Before that the record was 48047305725 × 2172403−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 × 2171960−1 with 51780 digits, found in May 2006. the above are still the six largest known Sophie Germain primes.
A heuristic
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
estimate (due to G. H. Hardy
G. H. Hardy
Godfrey Harold “G. H.” Hardy FRS was a prominent English mathematician, known for his achievements in number theory and mathematical analysis....
and J. E. Littlewood) for the number
Number
A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational numbers, irrational numbers, and complex numbers....
of Sophie Germain primes less than n is 2C2 n / (ln
Natural logarithm
The natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...
n)2 where C2 is the twin prime constant
Twin prime
A twin prime is a prime number that differs from another prime number by two. Except for the pair , this is the smallest possible difference between two primes. Some examples of twin prime pairs are , , , , and...
, 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. For n = 107, the estimate predicts 50822, which is still 10% off from the exact value of 56032.
A sequence {p, 2p + 1, 2(2p + 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
Cunningham chain
In mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham. They are also called chains of nearly doubled primes....
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
Safe prime
A safe prime is a prime number of the form 2p + 1, where p is also a prime. The first few safe primes are...
.
If a Sophie Germain prime p is congruent
Congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
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 mentioned in the stage play Proof
Proof (play)
Proof is a play by David Auburn originally produced by the Manhattan Theatre Club on 23 May 2000. It then went to Broadway on 24 October 2000 at the Walter Kerr Theatre, and was directed by Daniel J. Sullivan, with Mary-Louise Parker as Catherine, Larry Bryggman as Robert, Ben Shenkman as Hal, and...
and the subsequent film
Proof (2005 film)
Proof is a 2005 American drama film directed by John Madden and starring Anthony Hopkins, Gwyneth Paltrow, Jake Gyllenhaal, and Hope Davis; it was written by Rebecca Miller, based on David Auburn's Pulitzer Prize-winning play of the same title.-Plot:...
.
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). 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.See also
- PrimeGridPrimeGridPrimeGrid is a distributed computing project for searching for prime numbers of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing platform...
– search for Sophie Germain primes - Twin Prime SearchTwin Prime SearchTwin Prime Search is a distributed computing project that looks for large twin primes. It uses the programs LLR and NewPGen . It was founded on April 13, 2006 by Michael Kwok...
– includes search for Sophie Germain primes
External links
- The Top Twenty Sophie Germain Primes — from the Prime PagesPrime pagesThe Prime Pages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" lists for primes of various forms...
.