Generowanie dużych liczb pierwszych. Część 1

Czyli rzecz, która może się przydać w kryptografii.

Liczby pierwsze są dość problematyczne i można je generować na wiele sposobów. Z racji, że na liczby pierwsze nie istnieje żaden wzór (przynajmniej na początek roku 2015), to ich wygenerowanie sprowadza się do wygenerowania dużej liczby nieparzystej i sprawdzeniu czy jest to liczba pierwsza. Ogólny algorytm można zapisać w ten sposób:

  1. Wygeneruj dużą liczbę p.
  2. Sprawdź czy jest nieparzysta (jeżeli nie, to przejdź do kroku 1).
  3. Sprawdź czy jest liczbą pierwszą.

Algorytm w opisie jest maksymalnie prosty, lecz jest bardzo trudny w implementacji, problem tkwi w sprawdzeniu czy dana liczba jest liczbą pierwszą.

Najbardziej popularnym, a także najbardziej naturalnym dla nas programem będzie zastosowań własności liczb pierwszych znanych nam jeszcze ze szkoły podstawowej, czyli: liczba n jest liczbą pierwszą, gdy n = 2 lub nie istnieje taka liczba q z przedziału (2,n-1) że dzieli n. Inaczej mówiąc n jest podzielne tylko przez n i 1.

Kod jest niezwykle prosty i intuicyjny i faktycznie działa, dla liczby 29  podał właściwy wynik, czyli zwrócił informację że jest liczbą pierwszą, ale dla nieco większej liczby pierwszej ( 2147483647) sprawdzenie zajęło dużo więcej czasu i nic dziwnego skoro wykonujemy dla liczby n, ~n dzieleń.

Z tego powodów powstało (no może nie tylko z tego powodu) wiele testów pierwszości, które mają za zadanie sprawdzić czy dana jest liczbą pierwszą czy złożoną. Niektóre z nich mają za zadanie sprawdzić z pewnym prawdopodobieństwem (dokładnością) czy jest to liczba pierwsza, a  niektóre są w 100% dokładne.

Dzisiaj jednak zajmiemy się dużo prostszym (ale nie koniecznie łatwym) sposobem na sprawdzenie czy liczba jest pierwsza, jednocześnie będziemy posiadali 100% pewność do naszego wyniku. Co ważne nie będziemy działali na bardzo dużych liczbach lecz jedynie na tym przedziale na jaki zezwala nam obecnie c++, czyli [0, 18 446 744 073 709 551 615] jest to zakres liczb dla unsigned long long .

Skorzystamy z dość powszechnej własności w pisaniu programów, czyli aby coś sprawdzić czasami jest wygodniej i szybciej sprawdzić czy zachodzi negacja danego zdania logicznego.

A więc kiedy liczba NIE jest pierwsza? Gdy jest złożona. Czyli:

Ok, a więc mamy tutaj 2 sytuacje:

  1. Jeżeli a = b, to: a = sqrt(n) i b = sqrt(n).
  2. Jeżeli a != b, to: (a < sqrt(n) i b > sqrt(n)) lub (a > sqrt(n) i b < sqrt(n)).

Gdzie 2 case możemy skrócić zakładając, że a < b, ponieważ to lub dotyczy właśnie wariantów gdy a < b lub a > b.

Korzystając z tych warunków poszukujemy dzielnika z przedziału [2,sqrt(n)]. W ten sposób niwelujemy bardzo dużą ilość obliczeń i tak gdy wcześniej potrzebowaliśmy nieco ponad 1mln iteracji tak teraz potrzebujemy ich mniej więcej 1000.

Kod powyżej korzysta z tych własności i dla wcześniej problematycznej liczby ( 2147483647 ), którą sprawdzał dobre kilka sekund, teraz sprawdza w niecałą sekundę.

Z kolei nieco większą ( 1024628340621757567 )  posiadającą 19 cyfr sprawdza w 6 sekund, w przypadku pierwszej kodu chyba byśmy się nie doczekali 😉

Na większą już bardzo bliską granicy górnej naszego typu zmiennej 20 cyfrowego kolosa:  10168938831019335571 , program potrzebował już 11 sekund także widzimy, że w prawdziwej kryptografii przy naprawdę dużych liczbach by się już nie sprawdził, a dla naszych potrzeb to powinno wystarczyć (przy założeniu że skorzystamy jedynie z typów zmiennych dostępnych w standardowym c/c++). O lepszych sposobach sprawdzania pierwszości porozmawiamy kiedy indziej.

Jednakże generowanie takich liczb nie może być w 100% losowe (mówimy o liczbach 20 cyfrowych), gdyż szanse na trafienie na liczbą pierwszą nie są za duże, a wylosowanie jakiejś liczby i dojście do liczby pierwszej iteracyjnie nie jest zbyt dobrym pomysłem, bo pomiędzy 2 najmniejszymi (liczby wzięte stąd) 20 cyfrowymi liczbami pierwszymi musielibyśmy wykonać 110152200004639482 iteracji.

Zatem jak tego dokonać? O tym porozmawiamy w kolejnej części tego artykułu, a tymczasem zapraszam do komentowania.