Liczby pierwsze Germain

Liczba pierwsza Germain – w teorii liczb dowolna liczba pierwsza $p,$ dla której liczba $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 Szablon:OEIS. Przypuszczalnie istnieje nieskończenie wiele liczb pierwszych Germain, jednak do 2012 roku jest to problem otwarty. Największą znaną liczbą pierwszą Germain jest $2618163402417\cdot 2^{1290000}-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 $n$ wynosi $2C_2/(\ln (n){)}^2,$ gdzie $C_2$ jest stałą bliźniaczych liczb pierwszych, w przybliżeniu 0,660161. Dla $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 $n=10^7$ oszacowanie daje wynik 50822, a błąd wynosi 10% względem dokładnej wartości 56032.

Ciąg $\{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 $p$ przystaje do 3 (mod 4), to odpowiadająca jej liczba pierwsza $2p+1$ jest dzielnikiem liczby Mersenne’a $2^p-1.$

Generatory liczb pseudolosowych

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

Linki zewnętrzne

• The Top Twenty Sophie Germain Primes – from the Prime Pages.
• Szablon:MathWorld [dostęp 2022-07-02].