Przejdź do zawartości

Liczby pierwsze Germain

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Liczba pierwsza Germain)

Liczba pierwsza 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 publikacja w otwartym dostępie – możesz ją przeczytać 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 [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 wynosi gdzie jest stałą bliźniaczych liczb pierwszych, w przybliżeniu 0,660161. Dla 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 oszacowanie daje wynik 50822, a błąd wynosi 10% względem dokładnej wartości 56032.

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

Generatory liczb pseudolosowych

[edytuj | edytuj kod]

Liczby pierwsze 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 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 [online], primes.utm.edu [dostęp 2018-05-13] [zarchiwizowane z adresu 2016-06-07] (ang.).

Linki zewnętrzne

[edytuj | edytuj kod]