Liczba pierwsza Germain

Liczba pierwsza Germain – w teorii liczb dowolna liczba pierwsza ${\displaystyle p,}$ dla której liczba ${\displaystyle 2p+1}$ również jest pierwsza (np. 23, ponieważ 2 · 23 + 1 = 47 jest liczbą pierwszą); liczby te zostały nazwane na cześć Marie-Sophie Germain (ciąg A005384 w OEIS). Przypuszczalnie istnieje nieskończenie wiele liczb pierwszych Germain, jednak do 2012 roku jest to problem otwarty. Największą znaną liczbą pierwszą Germain jest ${\displaystyle 2618163402417\cdot 2^{1290000}-1}$^[1], 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 Germain (za G.H. Hardym i J.E. Littlewoodem) wśród liczb pierwszych mniejszych od ${\displaystyle n}$ wynosi ${\displaystyle 2C_{2}/(\ln(n))^{2},}$ gdzie ${\displaystyle C_{2}}$ jest stałą bliźniaczych liczb pierwszych, w przybliżeniu 0,660161. Dla ${\displaystyle n=10^{4}}$ to oszacowanie przewiduje istnienie 156 liczb pierwszych 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 ${\displaystyle n=10^{7}}$ oszacowanie daje wynik 50822, a błąd wynosi 10% względem dokładnej wartości 56032.

Ciąg ${\displaystyle \{p,2p+1,2(2p+1)+1,\dots \}}$ jednej lub więcej liczb pierwszych Germain, kończący się liczbą, która nie musi być liczbą pierwszą Germain, nazywana jest łańcuchem Cunninghama pierwszego rodzaju. Każdy wyraz tego ciągu, z wyjątkiem pierwszego i ostatniego, jest jednocześnie liczbą pierwszą Germain i bezpieczną liczbą pierwszą.

Jeśli liczba pierwsza Germain ${\displaystyle p}$ przystaje do 3 (mod 4), to odpowiadająca jej liczba pierwsza ${\displaystyle 2p+1}$ jest dzielnikiem liczby Mersenne’a ${\displaystyle 2^{p}-1.}$

Generatory liczb pseudolosowych

Liczby pierwsze Germain mają praktyczne zastosowanie w generowaniu liczb pseudolosowych. Rozwinięcie dziesiętne ${\displaystyle 1/q}$ tworzy ciąg ${\displaystyle q-1}$ pseudolosowych cyfr, o ile ${\displaystyle q}$ jest bezpieczną liczbą pierwszą liczby pierwszej Germain ${\displaystyle p,}$ przy ${\displaystyle p}$ przystającym do 3, 9, lub 11 (mod 20). Pasującymi liczbami pierwszymi ${\displaystyle q}$ są 7, 23, 47, 59, 167, 179 itd. (odpowiadają one ${\displaystyle p}$ = 3, 11, 23, 29, 83, 89 itd.). Wynik to ciąg ${\displaystyle q-1}$ cyfr, włączając wiodące zera. Dla przykładu, używając ${\displaystyle q}$ = 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

Linki zewnętrzne

• The Top Twenty Sophie Germain Primes – from the Prime Pages.
• Eric W.E.W. Weisstein Eric W.E.W., Sophie Germain Prime, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2022-07-02].