bigprimes2

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

Powrót do tematu po ponad połowie roku przerwy.

Na temat generowania liczb pierwszych mówiliśmy sobie w kontekście kryptografii, jeżeli ktoś jeszcze nie czytał poprzednich wpisów na ten temat to odsyłam do kategorii Kryptografia.

 

Czy moja liczba, jest liczbą pierwszą?


Uzyskanie odpowiedzi na to pytanie jest tak fantastycznym problemem, że testowanie procesorów odbywa się właśnie przez sprawdzanie pierwszości liczb.

Tutaj dzielimy algorytmy na 2 rodzaje:

  • deterministyczne – dane wyjściowe zależą całkowicie od danych wejściowych, co oznacza że zawsze po podstawieniu takich samych danych, otrzymamy identyczny wynik (dają 100% pewność poprawności wyniku);
  • probabilistyczne – otrzymany wynik jest prawdopodobnie poprawny, czyli przy identycznych danych wejściowych możemy otrzymać różny wynik.

Obecnie najczęściej stosowanymi są właśnie algorytmy probabilistyczne, które są po prostu o wiele szybsze w działaniu i pozwalają na otrzymanie niemal pewnego wyniku, a w razie konieczności upewnienia się czy nasza liczba jest pierwsza, można ją dodatkowo przetestować algorytmem deterministycznym.

W dalszej części chciałbym darować sobie historię powstawania algorytmów i ich głęboką analizę, na rzecz najważniejszych informacji o nich.

 

Test Millera-Rabina

Jest to zdecydowanie najczęściej używany algorytm probabilistyczny, jest szybki i daje stosunkowo dużą pewność otrzymania poprawnego wyniku (jego wariacji z algorytmem Lucasa używa choćby Mathematica).

Na wejściu otrzymuję liczbę n oraz parametr k określający dokładność testów. Prawdopodobieństwo otrzymania błędnego wyniku wynosi najwyżej 4^(-k), np dla k=5 istnieje maksymalnie 0.09765625% szans, że wynik jest błędny.

Jeżeli w algorytmie użyjemy algorytmu szybkiego potęgowania, to możemy zejść ze złożonością do O( k*(log n)^4 ).

Wejście
  • n – liczba nieparzysta, większa niż 1,
  • k – parametr decydujący o dokładności testu.
Wyjście
  • TRUE – liczba jest prawdopodobnie pierwsza,
  • FALSE – liczba jest złożona.
Lista kroków
  1. Wylicz (s) maksymalną potęgę dwójki dzielącą n-1.
  2. Przedstaw d w postaci: d = n/(2^s) .
  3. Powtórz k razy:
    1. wybierz losowo a ze zbioru {1, 2, … , n-1},
    2. sprawdź czy (a^d) mod n != 1
    3. jeżeli tak, to sprawdź czy a^(d*2^r) mod n != n-1 dla wszystkich r, ze zbioru {0, 1, …, r, …, s-1}
      • jeżeli tak, to zwróć FALSE.
  4. Jeżeli nie przerwano testu, to zwróć TRUE.

 

Test pierwszości AKS

Test pierwszości Agrawal-Kayal-Saxena jest algorytmem deterministycznym co oznacza, że daje 100% pewność otrzymanego wyniku. Ta metoda w porównaniu do poprzedniej jest dość nowa, bo została opublikowana w 2002 roku, w artykule zatytułowanym „PRIMES is in P”.

AKS działa w czasie wielomianowym (więc jest względnie szybki) oraz co ważne nie opiera się na twierdzeniach, które nie zostały do końca udowodnione.

Opiera się na uogólnionej wersji małego twierdzenia Fermata:

(x-a)^n  (x^n – a) (mod n)

Wejście
  • n – badana liczba, większa od 1.
Wyjście
  • TRUE – liczba jest pierwsza,
  • FALSE – liczba jest złożona.

 

Lista kroków
  1. Należy znaleźć taką liczbę pierwszą r = kq + 1, że:
    1. d(r-1) = q, gdzie d(x) największy dzielnik pierwszy x,
    2. q >= 4 sqrt(r) log_2 (n)
    3. n^k 1 mod r
    4. Jeżeli dla dowolnego p <= r, n jest podzielne przez p zwróć FALSE.
  2. Przeprowadź testy w pierścieniu wielomianów Z_n[x]/(x^r – 1) sprawdzając równości wielomianów:
    • (x-a)^n (x^na) (mod n,x^r – 1)
    • jeżeli dla wszystkich dodatnich a, takich że a <= 2 sqrt(r) log_2 (n) zachodzi identyczność zwróć TRUE, w przeciwnym razie FALSE.

 

Duże liczby = duży kłopot


Jak zapewne zauważyliście (albo zauważycie) to po implementacji tych algorytmów w większości języków programowania jesteśmy dość poważnie ograniczeni jeżeli chodzi o wielkość przechowywanych liczb i tak np w C jesteśmy w stanie przechować maksymalnie 64bitową liczbę, co się przekłada na maksymalnie 20 cyfr w systemie dziesiętnym.

Dzisiaj w kryptografii używa się nieco większych niż 64bitowych liczb, mianowicie: 1024 i 2048bitowych. Co z kolei stawia nowe wyzwanie, bo oprócz badania pierwszości liczb, ważną rzeczą jest także implementacja wydajnego systemu przechowującego liczby i operującego na nich (dodawanie, odejmowanie, przesuwanie bitów, …).

Ale tym już się nie zajmiemy w tym artykule, a może w przyszłych (ale nie obiecuję).

 

Podsumowanie


W tym wpisie zapoznaliśmy się z dwoma najlepszymi (pod pewnymi względami) algorytmami sprawdzania pierwszości. Zauważyliśmy także dość istotny problem jakim są ograniczenia związane ze standardami języków programowania.

Code ON!

 

Źródła
  • http://mathworld.wolfram.com/
  • http://www.numberphile.com/
  • http://www.aks.bluhost.pl/
  • https://www.wikipedia.org/

  • Pan Kulomb

    Bardzo interesujące. Czy mógłbyś robić wpisy dotyczące algorytmów skierowanych na OI 😀

    • Możesz powiedzieć czym jest OI?

    • Odpowiem ogólnie: chciałbym obecnie skupić się na kryptografii (i studiach), jednak jeżeli dostanę listę algorytmów, które chcielibyście żebym omówił to nie ma problemu (w większości przypadków).

  • Dawidek

    A może byś zrobił kurs jak zrobić jakiś jezyk programowania

    • Z tego co widzę to chyba trafiłeś do mnie z forum Zelenta (kojarzę prośby o to z forum). Mogę cię zapewnić, że takie coś się u mnie nie pojawi bo:
      1) Nie mam takiej ambicji.
      2) Obawiam się, że brakuje mi odpowiednich umiejętności, czy doświadczenia aby móc zrobić kurs o tym sensowny sposób (tak jak ktoś pisał: nie jest sztuką napisać język, który się wykonuje, sztuką jest zrobić go w taki sposób aby działał dobrze).
      3) Brakuje mi chęci i czasu (zrobienie czegoś takiego wymaga sporych nakładów pracy i czasu, a ja akurat mam zajęte wszystkie „sloty” na większe projekty, mogę jedynie od czasu do czasu zająć się czymś krótszym).
      4) Grupa odbiorców jest nieodpowiednia, zanim ktoś się obrazi: aby zrobić (pokazać) pewne rzeczy czy zagadnienia potrzebna jest grupa odbiorców w odpowiednim wieku, tzn taka która ma już pewną wiedzę ze szkół, czy uczelni.
      Zdaję sobie sprawę, że moi czytelnicy są głównie w wieku 14-18lat (przedział rozpina się na 11-35lat) dlatego chcę aby wiele zagadnień było pokazanych w ciekawy sposób także dla nich (np. to jest powodem dla którego temat kryptografii, RSA, liczb pierwszych został solidnie ucięty: nie chciałem wprowadzać ciał, pierścieni, itd).

      • Dawidek

        a umiez c#?

        • Nie powiedziałbym, że jestem wielkim znawcą tego języka, ale kilka projektów w nim napisałem.