Liczba pierwsza Sophie Germain

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Liczba pierwsza Sophie 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 (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ą do 2012 roku liczbą pierwszą Sophie Germain jest 18543637900515·2666667-1, a jej zapis dziesiętny wymaga 200701 cyfr; została znaleziona w kwietniu 2012 przez Philipa Bliedunga, 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 n wynosi 2 C2 / (ln n)2, gdzie C2 jest stałą bliźniaczych liczb pierwszych, w przybliżeniu 0,660161. Dla n = 104 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 n = 107 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, ...} 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 p przystaje do 3 (mod 4), to odpowiadająca jej liczba pierwsza 2p+1 jest dzielnikiem liczby Mersenne'a 2p-1.

Generatory liczb pseudolosowych[edytuj | edytuj kod]

Liczby pierwsze Sophie 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 Sophie 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ą ode 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[edytuj | edytuj kod]