Liczba pierwsza Sophie Germain

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Liczba pierwsza Sophie Germain – w teorii liczb dowolna liczba pierwsza dla której liczba 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 Sophie Germain, jednak do 2012 roku jest to problem otwarty. Największą znaną liczbą pierwszą Sophie Germain jest [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 Sophie Germain (za G.H. Hardym i J.E. Littlewoodem) wśród liczb pierwszych mniejszych od wynosi gdzie jest stałą bliźniaczych liczb pierwszych, w przybliżeniu 0,660161. Dla 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 oszacowanie daje wynik 50822, a błąd wynosi 10% względem dokładnej wartości 56032.

Ciąg 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ń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 przystaje do 3 (mod 4), to odpowiadająca jej liczba pierwsza jest dzielnikiem liczby Mersenne’a

Generatory liczb pseudolosowych[edytuj | edytuj kod]

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

  1. The Prime Database: 2618163402417*2^1290000-1, primes.utm.edu [dostęp 2018-05-13] (ang.).

Linki zewnętrzne[edytuj | edytuj kod]