Test pierwszości – 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 (2011 rok) nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.
Metoda naiwna
Najprostszy test pierwszości wygląda następująco: dla danej liczby n należy sprawdzić, 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 sprawdzić podzielność n przez liczby mniejsze lub równe pierwiastka(n)
Dowód. Załóżmy, że n jest złożona. Wtedy istnieją liczby a,b należące do N takie, że ab=N oraz a<=b Po przemnożeniu nierówności stronami przez a otrzymujemy a^2<=ab Ale ab=N więc a^2<=N Stąd a<=pierwiastek(N).
Kolejne udoskonalenie polega na sprawdzaniu podzielności n jedynie przez liczby pierwsze mniejsze lub równe pierwiastek(n) n. Ich listę łatwo możemy uzyskać metodą sita Eratostenesa. Metoda ta wciąż wymaga wykonania dużej liczby (pierwiastek(n)/log n) dzieleń, co oznacza, że już dla 50-cyfrowych liczb pierwszych jest niewykonalna na współczesnych komputerach.
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ć 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:
- Wybrać losowo liczbę a
- Sprawdzić pewne równanie zawierające a oraz zadaną liczbę n Jeśli okaże się fałszywe, zwrócić wynik n jest złożona. Wartość a jest wtedy świadkiem złożoności i test można zakończyć.
- Powtarzać całą procedurę, aż uzyska się 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 Solovaya-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.
Szybkie testy deterministyczne
Istnieje deterministyczny test pierwszości oparty o krzywe eliptyczne, działający w czasie O(log^6 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^4 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, zwany testem pierwszości AKS. Test ten w oryginalnej wersji działa w czasie O(log^12 n) choć w praktyce jest wolniejszy od metod probabilistycznych.