Sophie Germain prime

Sophie Germain prime

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, … OEIS|id=A005384.

The largest known Sophie Germain prime is 48047305725 × 2172403−1. It has 51910 decimal digits and was found by David Underbakke on January 25, 2007 using the programs TwinGen and LLR. [http://primes.utm.edu/primes/page.php?id=79261] The previous record was 137211941292195 × 2171960−1, which has 51780 decimal digits and was found by Járai et al. on May 3, 2006. [http://primes.utm.edu/primes/page.php?id=77705]

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

References

* Maximally Periodic Reciprocals, R.A.J. Matthews (1992). "Bulletin of the Institute of Mathematics and its Applications"; vol 28 pp 147-148.

External links

* [http://primes.utm.edu/top20/page.php?id=2 The Top Twenty Sophie Germain Primes] — from the Prime Pages.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Sophie Germain — This article is about the mathematician Marie Sophie Germain. See also Sophie Germain primes. Infobox Person name = Marie Sophie Germain caption = Marie Sophie Germain birth date = birth date|1776|4|1| birth place = Paris, France death date =… …   Wikipedia

  • Sophie-Germain-Primzahl — Eine Primzahl p nennt man Sophie Germain Primzahl oder auch Germainsche Primzahl, wenn auch 2p+1 eine Primzahl ist. Diese Primzahlen sind nach der Mathematikerin Sophie Germain (1776–1831) benannt, die sich mit der Fermatschen Vermutung… …   Deutsch Wikipedia

  • Nombre premier de Sophie Germain — Un nombre premier p est appelé un nombre premier de Sophie Germain si 2p + 1 est aussi un nombre premier. Ils ont reçu une signification en raison de la démonstration de Sophie Germain à propos de la véracité du dernier théorème de… …   Wikipédia en Français

  • Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) 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… …   Wikipedia

  • Germain, Sophie — ▪ French mathematician in full  Marie Sophie Germain  born April 1, 1776, Paris, France died June 27, 1831, Paris       French mathematician who contributed notably to the study of acoustics, elasticity, and the theory of numbers (number theory) …   Universalium

  • Safe prime — A safe prime is a prime number of the form 2 p + 1, where p is also a prime. (Conversely, the prime p is a Sophie Germain prime.) The first few safe primes are5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563,… …   Wikipedia

  • Mersenne prime — Named after Marin Mersenne Publication year 1536[1] Author of publication Regius, H. Number of known terms 47 Conjectured number of terms Infinite …   Wikipedia

  • List of prime numbers — This is an incomplete list, which may never be able to satisfy particular standards for completeness. You can help by expanding it with reliably sourced entries. By Euclid s theorem, there are an infinite number of prime numbers. Subsets of the… …   Wikipedia

  • Cuban prime — A cuban prime is a prime number that is a solution to one of two different specific equations involving third powers of x and y. The first of these equations is: and the first few cuban primes from this equation are (sequence A002407 in OEIS): 7 …   Wikipedia

  • 1000 (number) — List of numbers Integers ← 1k 2k 3k 4k 5k 6k 7k 8k 9k → Cardinal 1000 one thousand …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”