Test pierwszości

Z Wikipedii

Test pierwszości to algorytm określający czy dana liczba jest pierwsza czy złożona. 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 sprawdzać podzielność n przez liczby mniejsze lub równe .

Kolejne udoskonalenie polega na sprawdzaniu podzielności n jedynie przez liczby pierwsze mniejsze lub równe . 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 efektywne i najczęściej stosowane są testy probabilistyczne. Korzysta się w nich z losowo wygenerowanych liczb z ustalonego przedziału – pewien dobór tych wartości może dać w błędny wynik testu, ale przy wybraniu wystarczająco wielu z nich prawdopodobieństwo takiego zdarzenia jest znikome.

Przebieg testu probabilistycznego wygląda 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. Już sprawdzenie dwudziestu losowych świadków gwarantuje, że prawdopodobieństwo błędnego rozpoznania liczby jako pierwszej jest mniejsze niż jeden do biliona.

[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 skomplikowany w implementacji, ale prawdopodobnie jest to najczęściej używany deterministyczny test 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), choć w praktyce jest wolniejszy od metod probabilistycznych.

[edytuj] Złożoność

W teorii złożoności formalnie opisuje się język liczb pierwszych jako PRIMES. Można 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, pokazując że PRIMES leży w klasie P.