Editing Safe and Sophie Germain primes

{{Short description|Prime pair of the form (p, 2p+1)}}

In [[number theory]], a [[prime number]] ''p'' is a <span id="Sophie_Germain_prime">'''Sophie Germain prime'''</span> if 2''p''&nbsp;+&nbsp;1 is also prime. The number 2''p''&nbsp;+&nbsp;1 associated with a Sophie Germain prime is called a <span id="safe_prime">'''safe prime'''</span>. For example, 11 is a Sophie Germain prime and 2&thinsp;×&thinsp;11&nbsp;+&nbsp;1&nbsp;=&nbsp;23 is its associated safe prime. Sophie Germain primes and safe primes have applications in [[public key cryptography]] and [[primality testing]]. It has been [[conjecture]]d that there are [[infinite set|infinitely]] many Sophie Germain primes, but this remains unproven.

Sophie Germain primes are named after French mathematician [[Sophie Germain]], who used them in her investigations of [[Fermat's Last Theorem]].<ref>Specifically, Germain proved that the first case of Fermat's Last Theorem, in which the exponent divides one of the bases, is true for every Sophie Germain prime, and she used similar arguments to prove the same for all other primes up to 100. For details see {{citation|title=Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory|volume=50|series=Graduate Texts in Mathematics|first=Harold M.|last=Edwards|author-link=Harold Edwards (mathematician)|publisher=Springer|year=2000|isbn=9780387950020|pages=61–65}}.</ref> One attempt by Germain to prove Fermat’s Last Theorem was to let ''p'' be a prime number of the form 8''k'' + 7 and to let ''n'' = ''p'' – 1. In this case, <math>x^n + y^n = z^n</math> is unsolvable. Germain’s proof, however, remained unfinished.<ref name=":0">{{Cite journal |last=Dalmedico |first=Amy |date=1991 |title=Sophie Germain |url=https://www.jstor.org/stable/24938838 |journal=Scientific American |volume=265 |issue=6 |pages=116–123 |doi=10.1038/scientificamerican1291-116 |jstor=24938838 |bibcode=1991SciAm.265f.116D }}</ref><ref>{{Cite journal |last1=Laubenbacher |first1=Reinhard |last2=Pengelley |first2=David |date=2010-11-01 |title='Voici ce que j'ai trouvé:' Sophie Germain's grand plan to prove Fermat's Last Theorem |journal=Historia Mathematica |language=en |volume=37 |issue=4 |pages=641–692 |doi=10.1016/j.hm.2009.12.002 |issn=0315-0860|doi-access=free |arxiv=0801.1809 }}</ref> Through her attempts to solve Fermat's Last Theorem, Germain developed a result now known as Germain's Theorem which states that if ''p'' is an odd prime and 2''p'' + 1 is also prime, then ''p'' must divide ''x'', ''y'', or ''z.'' Otherwise, <math display="inline">x^n + y^n \neq z^n</math>. This case where ''p'' does not divide ''x'', ''y'', or ''z'' is called the first case. Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time.<ref name=":0" /> Later work by [[Ernst Kummer|Kummer]] and others always divided the problem into first and second cases.

==Individual numbers==
The first few Sophie Germain primes (those less than 1000) are

: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, ... {{OEIS2C|id=A005384}}

Hence, the first few safe primes are

:5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, ... {{OEIS2C|id=A005385}}

In [[cryptography]], much larger Sophie Germain primes like 1,846,389,521,368 + 11<sup>600</sup> are required.

Two distributed computing projects, [[PrimeGrid]] and [[Twin Prime Search]], include searches for large Sophie Germain primes. Some of the largest known Sophie Germain primes are given in the following table.<ref>[http://primes.utm.edu/top20/page.php?id=2 The Top Twenty Sophie Germain Primes]&nbsp;— from the [[Prime Pages]]. Retrieved 17 May 2020.</ref>
{| class="wikitable"
|-
! Value !! Number<br>of&nbsp;digits !! Time of<br>discovery !! Discoverer
|-
| 2618163402417 × 2<sup>1290000</sup> − 1 || align="right" | 388342 || February 2016 || Dr. James Scott Brown in a distributed [[PrimeGrid]] search using the programs TwinGen and [[Lucas–Lehmer–Riesel test|LLR]]<ref>{{cite web|title=PrimeGrid's Sophie Germain Prime Search|url=https://www.primegrid.com/download/SGS_2618163402417_1290000.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.primegrid.com/download/SGS_2618163402417_1290000.pdf |archive-date=2022-10-09 |url-status=live|publisher=PrimeGrid|access-date=29 February 2016}}</ref>
|-
| 18543637900515 × 2<sup>666667</sup> − 1 || align="right" | 200701 || April 2012 || Philipp Bliedung in a distributed [[PrimeGrid]] search using the programs TwinGen and [[Lucas–Lehmer–Riesel test|LLR]]<ref>{{cite web|title=PrimeGrid's Sophie Germain Prime Search|url=http://www.primegrid.com/download/SGS_666667.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.primegrid.com/download/SGS_666667.pdf |archive-date=2022-10-09 |url-status=live|publisher=PrimeGrid|access-date=18 April 2012}}</ref>
|-
|183027 × 2<sup>265440</sup> − 1 || align="right" | 79911 || March 2010 || Tom Wu using LLR<ref>[http://primes.utm.edu/primes/page.php?id=92222 The Prime Database: 183027*2^265440-1]. From The [[Prime Pages]].</ref>
|-
|style="white-space:nowrap"|648621027630345 × 2<sup>253824</sup> − 1 and<br>620366307356565 × 2<sup>253824</sup> − 1 || align="right" | 76424 ||style="white-space:nowrap"| November 2009 || Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza and Antal Járai<ref>[http://primes.utm.edu/primes/page.php?id=90907 The Prime Database: 648621027630345*2^253824-1].</ref><ref>[http://primes.utm.edu/primes/page.php?id=90711 The Prime Database: 620366307356565*2^253824-1]</ref>
|-
|1068669447 × 2<sup>211088</sup> − 1 || align="right" | 63553 || May 2020 || Michael Kwok<ref>[https://primes.utm.edu/primes/page.php?id=130903 The Prime Database: 1068669447*2^211088-1] From The [[Prime Pages]].</ref>
|-
|99064503957 × 2<sup>200008</sup> − 1 || align="right" | 60220 || April 2016 || S. Urushihata<ref>[https://primes.utm.edu/primes/page.php?id=121507 The Prime Database: 99064503957*2^200008-1] From The [[Prime Pages]].</ref>
|-
|607095 × 2<sup>176311</sup> − 1 || align="right" | 53081 ||style="white-space:nowrap"| September 2009 || Tom Wu<ref>[http://primes.utm.edu/primes/page.php?id=89999 The Prime Database: 607095*2^176311-1].</ref>
|-
|48047305725 × 2<sup>172403</sup> − 1 || align="right" | 51910 || January 2007 || David Underbakke using TwinGen and LLR<ref>[http://primes.utm.edu/primes/page.php?id=79261 The Prime Database: 48047305725*2^172403-1].</ref>
|-
|style="white-space:nowrap"|137211941292195 × 2<sup>171960</sup> − 1 || align="right" | 51780 || May 2006 || Járai et al.<ref>[http://primes.utm.edu/primes/page.php?id=77705 The Prime Database: 137211941292195*2^171960-1].</ref>
|-
|}

On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a [[discrete logarithm]] modulo the 240-digit (795 bit) prime RSA-240 + 49204 (the first safe prime above RSA-240) using a [[General number field sieve|number field sieve]] algorithm; see [[Discrete logarithm records]].

==Properties==
There is no special primality test for safe primes the way there is for [[Fermat prime]]s and [[Mersenne prime]]s. However, [[Pocklington primality test|Pocklington's criterion]] can be used to prove the primality of 2''p'' + 1 once one has proven the primality of ''p''. 

Just as every term except the last one of a [[Cunningham chain]] of the first kind is a Sophie Germain prime, so every term except the first of such a chain is a safe prime. Safe primes ending in 7, that is, of the form 10''n''&nbsp;+&nbsp;7, are the last terms in such chains when they occur, since 2(10''n''&nbsp;+&nbsp;7)&nbsp;+&nbsp;1 = 20''n''&nbsp;+&nbsp;15 is [[divisibility|divisible]] by 5.

For a safe prime, every [[quadratic nonresidue]], except −1 (if nonresidue{{efn|−1 is a quadratic residue only when the safe prime is equal 5; for all other safe primes, −1 is a nonresidue}}), is a [[Primitive root modulo n|primitive root]]. It follows that for a safe prime, the least positive primitive root is a prime number.<ref>{{cite journal|vauthors=Ramesh VP, Makeshwari M|title=Least Primitive Root of any Safe Prime is Prime|journal=The American Mathematical Monthly|issue=10|volume=129|date=16 September 2022|page=971 |doi=10.1080/00029890.2022.2115816}}</ref>

===Modular restrictions===
With the exception of 7, a safe prime ''q'' is of the form 6''k''&nbsp;&minus;&nbsp;1 or, equivalently, ''q'' ≡ 5 ([[modulo operation|mod]] 6) – as is ''p'' > 3. Similarly, with the exception of 5, a safe prime ''q'' is of the form 4''k''&nbsp;&minus;&nbsp;1 or, equivalently, ''q'' ≡ 3 (mod 4) — trivially true since (''q''&nbsp;&minus;&nbsp;1) / 2 must evaluate to an [[parity (mathematics)|odd]] [[natural number]]. Combining both forms using [[least common multiple|lcm]](6, 4) we determine that a safe prime ''q'' > 7 also must be of the form 12''k'' − 1 or, equivalently, ''q'' ≡ 11 (mod 12).

It follows that, for any safe prime ''q'' > 7:
* both 3 and 12 are [[quadratic residue]]s mod ''q'' (per [[Quadratic residue#Law of quadratic reciprocity|law of quadratic reciprocity]]) <!-- this wikilink to a section is used to provide easy access to the table in the section, specifically a = 3 and a = 12 rows -->
** neither 3 nor 12 is a [[Primitive root modulo n|primitive root]] of ''q''
** the only safe primes that are also [[full reptend prime]]s in [[base 12]] are 5 and 7
** ''q'' divides 3<sup>(''q''−1)/2</sup> − 1 and 12<sup>(''q''−1)/2</sup> − 1, same as 3<sup>(''q''−1)/2</sup> ≡ 1 mod ''q'' and 12<sup>(''q''−1)/2</sup> ≡ 1 mod ''q'' (per [[Euler's criterion]])
* ''q''&nbsp;−&nbsp;3, ''q''&nbsp;−&nbsp;4, ''q''&nbsp;−&nbsp;9, ''q''&nbsp;−&nbsp;12 are quadratic nonresidues <!-- see the table at  [[Quadratic residue#Law of quadratic reciprocity]] -->
** ''q''&nbsp;−&nbsp;3, ''q''&nbsp;−&nbsp;4, ''q''&nbsp;−&nbsp;9, and, for ''q'' > 11, ''q''&nbsp;−&nbsp;12 are primitive roots <!-- as all nonresidues, except −1, are primitive roots for safe primes -->
If ''p'' is a Sophie Germain prime greater than&nbsp;3, then ''p'' must be congruent to 2&nbsp;mod&nbsp;3. For, if not, it would be congruent to 1&nbsp;mod&nbsp;3 and 2''p''&nbsp;+&nbsp;1 would be congruent to 3&nbsp;mod&nbsp;3, impossible for a prime number.<ref>{{citation|title=An Episodic History of Mathematics: Mathematical Culture Through Problem Solving|publisher=Mathematical Association of America|first=Steven G.|last=Krantz|year=2010|isbn=9780883857663|page=206|url=https://books.google.com/books?id=ulmAH-6IzNoC&pg=PA206}}.</ref> Similar restrictions hold for larger prime moduli, and are the basis for the choice of the "correction factor" 2''C'' in the Hardy–Littlewood estimate on the density of the Sophie Germain primes.<ref name="shoup"/>

If a Sophie Germain prime ''p'' is [[Congruence relation|congruent]] to 3 (mod 4) ({{oeis|id=A002515}}, ''Lucasian primes''), then its matching safe prime 2''p''&nbsp;+&nbsp;1 ([[modular arithmetic|congruent]] to 7 modulo 8) will be a divisor of the [[Mersenne number]]&nbsp;2<sup>''p''</sup>&nbsp;−&nbsp;1. Historically, this result of [[Leonhard Euler]] was the first known criterion for a Mersenne number with a prime index to be [[composite number|composite]].<ref>{{citation
 | last = Ribenboim | first = P. | author-link = Paulo Ribenboim
 | doi = 10.1007/BF03023623
 | issue = 2
 | journal = [[The Mathematical Intelligencer]]
 | mr = 737682
 | pages = 28–34
 | title = 1093
 | volume = 5
 | year = 1983}}.</ref> It can be used to generate the largest Mersenne numbers (with prime indices) that are known to be composite.<ref>{{citation|title=Large Sophie Germain primes|first=Harvey|last=Dubner|author-link=Harvey Dubner|journal=Mathematics of Computation|volume=65|year=1996|issue=213 |pages=393–396|doi=10.1090/S0025-5718-96-00670-9|mr=1320893|citeseerx=10.1.1.106.2395}}.</ref>

==Infinitude and density==
{{unsolved|mathematics|Are there infinitely many Sophie Germain primes?}}
It is [[conjecture]]d that there are infinitely many Sophie Germain primes, but this has not been [[mathematical proof|proven]].<ref name="shoup">{{citation|title=A Computational Introduction to Number Theory and Algebra|first=Victor|last=Shoup|author-link=Victor Shoup|publisher=Cambridge University Press|year=2009|isbn=9780521516440|contribution=5.5.5 Sophie Germain primes|pages=123–124|url=https://books.google.com/books?id=pWFdMf5hb5oC&pg=PA123}}.</ref> 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<ref name="shoup"/>
:<math>2C \frac{n}{(\ln n)^2} \approx 1.32032\frac{n}{(\ln n)^2}</math>
where
:<math>C=\prod_{p>2} \frac{p(p-2)}{(p-1)^2}\approx 0.660161</math>
is [[Twin prime#First Hardy–Littlewood conjecture|Hardy–Littlewood's twin prime constant]]. For ''n''&nbsp;=&nbsp;10<sup>4</sup>, this estimate predicts 156 Sophie Germain primes, which has a 20% error compared to the exact value of 190. For ''n''&nbsp;=&nbsp;10<sup>7</sup>, 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 prime]]s.<ref>{{citation|title=Fermat's Last Theorem for Amateurs|first=Paulo|last=Ribenboim|author-link=Paulo Ribenboim|publisher=Springer|year=1999|isbn=9780387985084|page=141|url=https://books.google.com/books?id=XPrQmE5trIgC&pg=PA141}}.</ref>

A [[integer sequence|sequence]] (''p'', 2''p''&nbsp;+&nbsp;1, 2(2''p''&nbsp;+&nbsp;1)&nbsp;+&nbsp;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,<ref>{{citation|title=Prime Numbers: The Most Mysterious Figures in Math|first=David|last=Wells|publisher=John Wiley & Sons|year=2011|isbn=9781118045718|page=35|url=https://books.google.com/books?id=1MTcYrbTdsUC&pg=PA35|quote=If the strong prime ''k''-tuples conjecture is true, then Cunningham chains can reach any length.}}</ref> although infinite chains are known to be impossible.<ref>{{citation|last=Löh|first=Günter|title=Long chains of nearly doubled primes|journal=[[Mathematics of Computation]]|year=1989|volume=53|issue=188|pages=751–759|doi=10.1090/S0025-5718-1989-0979939-8|mr=0979939|doi-access=free}}.</ref>

==Strong primes==
A prime number ''q'' is a [[strong prime]] if {{nowrap|''q'' + 1}} and {{nowrap|''q'' − 1}} both have some large (around 500 digits) prime factors. For a safe prime {{nowrap|1=''q'' = 2''p'' + 1}}, the number {{nowrap|''q'' − 1}} naturally has a large prime factor, namely ''p'', and so a safe prime ''q'' meets part of the criteria for being a strong prime. The running times of some methods of [[integer factorization|factoring]] a number with ''q'' as a prime factor depend partly on the size of the prime factors of {{nowrap|''q'' − 1}}. This is true, for instance, of the [[Pollard's p − 1 algorithm|''p'' − 1 method]].

==Applications==

===Cryptography===
Safe primes are also important in cryptography because of their use in [[discrete logarithm]]-based techniques like [[Diffie–Hellman key exchange]]. If {{nowrap|2''p'' + 1}} is a safe prime, the multiplicative [[group (mathematics)|group]] of integers [[modular arithmetic|modulo]] {{nowrap|2''p'' + 1}} has a [[subgroup]] of large prime [[order (group theory)|order]]. It is usually this prime-order subgroup that is desirable, and the reason for using safe primes is so that the modulus is as small as possible relative to ''p''.  

A prime number ''p''&nbsp;=&nbsp;2''q''&nbsp;+&nbsp;1 is called a ''safe prime'' if ''q'' is prime. Thus, ''p''&nbsp;=&nbsp;2''q''&nbsp;+&nbsp;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''&nbsp;−&nbsp;1 and ''p''&nbsp;+&nbsp;1 have large prime factors. Safe and strong primes were useful as the factors of secret keys in the [[RSA_(cryptosystem)|RSA cryptosystem]], because they prevent the system being broken by some [[Integer factorization|factorization]] algorithms such as [[Pollard's p − 1 algorithm|Pollard's ''p'' − 1 algorithm]]. However, with the current factorization technology, the advantage of using safe and strong primes appears to be negligible.<ref>{{citation|title=Are 'strong' primes needed for RSA?|first1=Ronald L.|last1=Rivest|first2=Robert D.|last2=Silverman|date=November 22, 1999|url=https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf |archive-date=2022-10-09 |url-status=live}}</ref>

Similar issues apply in other cryptosystems as well, including [[Diffie–Hellman key exchange]] and similar systems that depend on the security of the [[discrete logarithm problem]] rather than on integer factorization.<ref>{{citation
 | last = Cheon | first = Jung Hee | author-link = Cheon Jung-Hee
 | contribution = Security analysis of the strong Diffie–Hellman problem
 | doi = 10.1007/11761679_1
 | pages = 1–11
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06), St. Petersburg, Russia, May 28 – June 1, 2006, Proceedings
 | volume = 4004
 | year = 2006| url = http://www.iacr.org/cryptodb/archive/2006/EUROCRYPT/2143/2143.pdf| doi-access = free
 | isbn = 978-3-540-34546-6 }}.</ref> 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.<ref>{{citation
 | last = Gordon | first = John A.
 | contribution = Strong primes are easy to find
 | doi = 10.1007/3-540-39757-4_19
 | pages = 216–223
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proceedings of EUROCRYPT 84, A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 9–11, 1984
 | volume = 209
 | year = 1985| doi-access = free
 | isbn = 978-3-540-16076-2
 }}.</ref>

In [[Sophie Germain Counter Mode]], it was proposed to use the arithmetic in the [[finite field]] of order equal to the safe prime 2<sup>128</sup>&nbsp;+&nbsp;12451, to counter weaknesses in [[Galois/Counter Mode]] using the binary finite field GF(2<sup>128</sup>). However, SGCM has been shown to be vulnerable to many of the same cryptographic attacks as GCM.<ref>{{citation
 | last1 = Yap | first1 = Wun-She
 | last2 = Yeo | first2 = Sze Ling
 | last3 = Heng | first3 = Swee-Huay
 | last4 = Henricksen | first4 = Matt
 | doi = 10.1002/sec.798
 | journal = Security and Communication Networks
 | title = Security analysis of GCM for communication
 | year = 2013| volume = 7
 | issue = 5
 | pages = 854–864
 | doi-access = 
 }}.</ref>

===Primality testing===
In the first version of the [[AKS primality test]] paper, a conjecture about Sophie Germain primes is used to lower the worst-case complexity from {{math|O(log<sup>12</sup>''n'')}} to {{math|O(log<sup>6</sup>''n'')}}. A later version of the paper is shown to have time complexity {{math|O(log<sup>7.5</sup>''n'')}} which can also be lowered to {{math|O(log<sup>6</sup>''n'')}} using the conjecture.<ref>{{citation |first1=Manindra |last1=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |archive-date=2022-10-09 |url-status=live |title=PRIMES is in P |journal=[[Annals of Mathematics]] |volume=160 |year=2004 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 |doi-access=free }}</ref> Later variants of AKS have been proven to have complexity of {{math|O(log<sup>6</sup>''n'')}} without any conjectures or use of Sophie Germain primes.

===Pseudorandom number generation===
Safe primes obeying certain congruences can be used to generate [[pseudo-random numbers]] of use in [[Monte Carlo simulation]].

Similarly, Sophie Germain primes may be used in the generation of [[pseudo-random numbers]]. The decimal expansion of 1/''q'' will produce a [[Recurring decimal#Fractions with prime denominators|stream]] of ''q''&nbsp;−&nbsp;1 pseudo-random digits, if ''q'' is the safe prime of a Sophie Germain prime ''p'', with ''p'' [[Modular_arithmetic#Congruence|congruent]] to 3, 9, or 11 modulo 20.<ref>{{citation
 | last = Matthews | first = Robert A. J.
 | issue = 9–10
 | journal = Bulletin of the Institute of Mathematics and Its Applications
 | mr = 1192408
 | pages = 147–148
 | title = Maximally periodic reciprocals
 | volume = 28
 | year = 1992}}.</ref> Thus "suitable" prime numbers ''q'' are 7, 23, 47, 59, 167, 179, etc. ({{oeis|id=A000353}}) (corresponding to ''p''&nbsp;=&nbsp;3,&nbsp;11,&nbsp;23,&nbsp;29,&nbsp;83,&nbsp;89,&nbsp;etc.) ({{oeis|id=A000355}}). The result is a stream of [[period length|length]] ''q''&nbsp;−&nbsp;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.{{cn|date=June 2020}}

==In popular culture==
Sophie Germain primes are mentioned in the stage play ''[[Proof (play)|Proof]]''<ref>{{citation|title=Drama in numbers: putting a passion for mathematics on stage|first=Ivars|last=Peterson|author-link=Ivars Peterson|journal=[[Science News]]|date=Dec 21, 2002|doi=10.2307/4013968 |jstor=4013968 |url=http://www.thefreelibrary.com/Drama+in+numbers%3A+putting+a+passion+for+mathematics+on+stage.-a096417274|quote=[Jean E.] Taylor pointed out that the example of a Germain prime given in the preliminary text was missing the term "+ 1."  "When I first went to see 'Proof' and that moment came up in the play, I was happy to hear the 'plus one' clearly spoken," Taylor says.}}</ref> and the [[Proof (2005 film)|subsequent film]].<ref>{{citation|url=http://www.ams.org/notices/200603/rev-ullman.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.ams.org/notices/200603/rev-ullman.pdf |archive-date=2022-10-09 |url-status=live|title=Movie Review: Proof|first=Daniel|last=Ullman|journal=[[Notices of the AMS]]|volume=53|issue=3|year=2006|pages=340–342|quote=There are a couple of breaks from realism in ''Proof'' where characters speak in a way that is for the benefit of the audience rather than the way mathematicians would actually talk among themselves. When Hal (Harold) remembers what a Germain prime is, he speaks to Catherine in a way that would be patronizing to another mathematician.}}</ref>

==Notes==
{{notelist}}

==References==
{{reflist|30em}}

==External links==
* {{PlanetMath |urlname=SafePrime |title=Safe prime}}
* {{cite book |editor=[[M. Abramowitz]], [[I. A. Stegun]] |title=Handbook of Mathematical Functions |publisher=National Bureau of Standards |series=Applied Math. Series |volume=55 |edition=Tenth Printing |year=1972 |pages=870 |url=http://www.math.sfu.ca/~cbm/aands/}}

{{Prime number classes}}

{{DEFAULTSORT:Sophie Germain Prime}}
[[Category:Classes of prime numbers]]
[[Category:Unsolved problems in number theory]]