Test pierwszości

Z Wikipedii

Test pierwszości to algorytm określający czy dana liczba jest pierwsza czy złożona. Należy pamiętać że nie jest to równoważne znalezieniu jej rozkładu na czynniki pierwsze. W obecnej chwili (2006 rok), nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.

Spis treści 1 Metoda naiwna 2 Testy probabilistyczne 3 Szybkie testy deterministyczne 4 Złożoność

[edytuj] Metoda naiwna

Najprostszy test pierwszości wygląda następująco: Dla danej liczby n sprawdzamy czy dzieli się ona kolejno przez 2,3, aż do n-1. Jeśli przez żadną z nich się nie dzieli, oznacza to że jest pierwsza.

Zamiast testować wszystkie liczby do n-1, wystarczy że sprawdzimy je do : jeśli n jest złożona, to musi mieć jakiś dzielnik nie większy niż .

Ponadto możemy zwiększyć efektywność naszego testu pomijając wszystkie parzyste liczby poza 2 - gdyż jeśli n nie dzieli się przez 2 to nie dzieli się przez żadną liczbę parzystą. Analogicznie możemy po sprawdzeniu 3 pominąć wszystkie jej wielokrotności itd. Ostatecznie zauważamy że wystarczy sprawdzić jedynie liczby pierwsze mniejsze od . Ich listę łatwo możemy uzyskać metodą Sita Eratostenesa.

Metoda ta niestety wciąż wymaga wykonania dużej ilości () dzieleń, co oznacza że już dla 50-cyfrowych liczb pierwszych jest niewykonalna na współczesnych komputerach.

[edytuj] Testy probabilistyczne

Obecnie najbardziej efektywnymi i najczęściej stosowanymi testatmi są testy probabilistyczne. W takich testach korzysta się z losowo wygenerowanych liczb z ustalonego przedziału. Odpowiednio pechowy dobór tych wartości może spowodować błędny wynik testu, ale przy wybraniu wystarczająco wielu z nich prawdopodobieństwo takiego zdarzenia jest znikome.

Testy te wyglądają następująco:

1. Wybierz losowo liczbę a
2. Sprawdź pewne równanie zawierające a oraz zadaną liczbę n. Jeśli okaże się fałszywe, zwróć wynik n jest złożona. Wartość a jest wtedy świadkiem złożoności i test można zakończyć.
3. Powtarzaj całą procedurę aż uzyskasz wystarczającą pewność.

Jeśli w wystarczająco wielu próbach nie uda się stwierdzić złożoności n, test zwraca odpowiedź n jest prawdopodobnie pierwsza.

Najbardziej znanymi testami pierwszości są:

• Test pierwszości Fermata – prosty do przeprowadzenia, ale niepewny: istnieją liczby złożone (Liczby Carmichaela) które przez ten test zawsze zostaną uznane za pierwsze.

• Test pierwszości Solovay-Strassena – dający przy każdej próbie 1/2 szans na wylosowanie świadka złożoności.

• Test Millera-Rabina – dający przy każdej próbie 3/4 szans na wylosowanie świadka złożoności. Ten test jest najczęściej stosowany w kryptografii, gdy wymagana jest szybka weryfikacja pierwszości dużych liczb. Przykładowo sprawdzenie dwudziestu losowych świadków daje już prawdopodobieństwo mniejsze niż jeden do biliona że test da nieprawidłową odpowiedź.

[edytuj] Szybkie testy deterministyczne

Istnieje deterministyczny test pierwszości oparty o krzywe eliptyczne, działający w czasie O(log⁶n). Jego działanie opiera się jednak na pewnych dotychczas nieudowodnionych twierdzeniach z teorii liczb. Jest on skomplikowanym w implementacji, ale prawdopodobnie najczęściej używanym deterministycznym testem pierwszości.

Jeśli uogólniona hipoteza Riemanna jest prawdziwa, test Millera-Rabina można przekształcić w test deterministyczny, działający w czasie O(log⁴n). W praktyce jest on jednak wolniejszy od poprzedniego.

W 2002 roku, Manindra Agrawal, Nitin Saxena i Neeraj Kayal opublikowali pierwszy deterministyczny wielomianowy test nie opierający się na żadnych niedowiedzionych założeniach (test pierwszości AKS). Test ten w oryginalnej wersji działa w czasie O(log¹²n), dowodząc tym samym że liczby pierwsze można weryfikować w sposób pewny w czasie wielomianowym. W praktyce algorytm ten jest jednak wolniejszy od metod probabilistycznych.

[edytuj] Złożoność

W teorii złożoności, formalnie opisuje się język liczb pierwszych jako PRIMES. Łatwo pokazać że PRIMES należy do klasy coNP: jego dopełnienie COMPOSITES należy do NP, gdyż można łatwo niedeterministycznie stwierdzić że jakaś liczba jest złożona - zgadując jej dzielniki.

W 1975 roku, Vaughan Ronald Pratt pokazał że istnieją certyfikaty pierwszości: sprawdzalne w czasie wielomianowym dowody że dana liczba jest pierwsza. Tym samym udowodnił że język PRIMES należy też do klasy NP, a więc należy do przecięcia NP ∩ coNP.

Kolejne algorytmy Solovay-Strassena i Millera-Rabina umieściły język PRIMES w klasie coRP. W 1992, algorytm Adlemana-Huanga zmniejszył złożoność problemu do ZPP = RP ∩ coRP, poprawiając wynik Pratta.

Ostatecznie opracowanie algorytmu AKS zamknęło ten problem, udowadniając że PRIMES leży w klasie P.