|
'''Liczba pierwsza Sophie Germain''' – w [[Teoria liczb|teorii liczb]] dowolna [[liczba pierwsza]] <math>p,</math> dla której liczba <math>2p + 1</math> również jest pierwsza (np. 23, ponieważ 2 · 23 + 1 = 47 jest liczbą pierwszą); liczby te zostały nazwane na cześć [[Sophie Germain|Marie-Sophie Germain]] {{OEIS|id=A005384}}. Przypuszczalnie istnieje [[Nieskończoność|nieskończenie]] wiele liczb pierwszych Sophie Germain, jednak do 2012 roku jest to [[nierozwiązane problemy w matematyce|problem otwarty]]. Największą znaną liczbą pierwszą Sophie Germain jest <math>2618163402417\cdot 2^{1290000} - 1</math><ref>{{Cytuj |url=http://primes.utm.edu/primes/page.php?id=121330 |tytuł=The Prime Database: 2618163402417*2^1290000-1<!-- Tytuł wygenerowany przez bota --> |opublikowany=primes.utm.edu |język=en |data dostępu=2018-05-13}}</ref>, a jej zapis dziesiętny wymaga 388342 cyfr; została znaleziona 29 lutego 2016 przez urządzenie Xeon 4c+4c, podczas rozproszonych obliczeń w ramach projektu [[PrimeGrid]], przy użyciu programów TwinGen oraz LLR.
Heurystyczne oszacowanie ilości liczb pierwszych Sophie Germain (za [[Godfrey Harold Hardy|G.H. Hardym]] i [[John Edensor Littlewood|J.E. Littlewoodem]]) wśród liczb pierwszych mniejszych od <math>n</math> wynosi <math>2C_2 / (\ln (n))^2,</math> gdzie <math>C_2</math> jest stałą bliźniaczych liczb pierwszych, w przybliżeniu 0,660161. Dla <math>n = 10^4</math> to oszacowanie przewiduje istnienie 156 liczb pierwszych Sophie Germain, co jest wartością o 20% mniejszą od faktycznej ilości tych liczb w przedziale, wynoszącą 190. Natomiast dla większej próbki <math>n = 10^7</math> oszacowanie daje wynik 50822, a błąd wynosi 10% względem dokładnej wartości 56032.
Ciąg <math>\{p, 2p+1, 2 (2p+1)+1, \dots\}</math> jednej lub więcej liczb pierwszych Sophie Germain, kończący się liczbą, która nie musi być liczbą pierwszą Sophie Germain, nazywana jest [[łańcuch Cunninghama|łańcuchem Cunninghama]] pierwszego rodzaju. Każdy wyraz tego ciągu, z wyjątkiem pierwszego i ostatniego, jest jednocześnie liczbą pierwszą Sophie Germain i bezpieczną liczbą pierwszą.
Jeśli liczba pierwsza Sophie Germain <math>p</math> przystaje do 3 (mod 4), to odpowiadająca jej liczba pierwsza <math>2p + 1</math> jest dzielnikiem [[liczby Mersenne’a]] <math>2^p - 1.</math>
== Generatory liczb pseudolosowych ==
Liczby pierwsze Sophie Germain mają praktyczne zastosowanie w [[generator liczb pseudolosowych|generowaniu liczb pseudolosowych]]. Rozwinięcie dziesiętne <math>1/q</math> tworzy ciąg <math>q - 1</math> pseudolosowych cyfr, o ile <math>q</math> jest bezpieczną liczbą pierwszą liczby pierwszej Sophie Germain <math>p,</math> przy <math>p</math> przystającym do 3, 9, lub 11 (mod 20). Pasującymi liczbami pierwszymi <math>q</math> są 7, 23, 47, 59, 167, 179 itd. (odpowiadają one <math>p</math> = 3, 11, 23, 29, 83, 89 itd.). Wynik to ciąg <math>q - 1</math> cyfr, włączając wiodące zera. Dla przykładu, używając <math>q</math> = 23, wygenerowany zostanie następujący ciąg: 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3. Liczby te nie nadają się do zastosowań kryptograficznych, ponieważ wartość każdej kolejnej można obliczyć używając jej poprzedników.
== Przypisy ==
|
