Test pierwszości

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 ${\sqrt {n}}.$

Dowód. Załóżmy, że $n$ jest złożona. Wtedy istnieją liczby $a,b\in \mathbb {N}$ takie, że $n=ab$ oraz $a\leqslant b.$ Po przemnożeniu nierówności stronami przez $a$ otrzymujemy $a^{2}\leqslant ab.$ Ale $ab=n,$ więc $a^{2}\leqslant n.$ Stąd $a\leqslant {\sqrt {n}}.$

Kolejne udoskonalenie polega na sprawdzaniu podzielności $n$ jedynie przez liczby pierwsze mniejsze lub równe ${\sqrt {n}}.$ Ich listę łatwo możemy uzyskać metodą sita Eratostenesa. Metoda ta wciąż wymaga wykonania dużej liczby $({\sqrt {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:

1. Wybrać losowo liczbę $a.$
2. 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ć.
3. 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 $\mathrm {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 $\mathrm {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 $\mathrm {O} (\log ^{12}n)$ choć w praktyce jest wolniejszy od metod probabilistycznych.

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 (jego dopełnienie należy do RP, czyli klasy problemów, dla których istnieje probabilistyczna maszyna Turinga działająca w czasie wielomianowym, która zwraca „nie” zawsze, kiedy prawidłową odpowiedzią jest „nie”, i zwraca „tak” (z prawdopodobieństwem, które dla żadnych danych nie spada poniżej pewnej wartości) lub „nie”, kiedy prawidłową odpowiedzią jest „tak”). W 1992 roku algorytm Adlemana-Huanga zmniejszył złożoność problemu do ZPP = RP ∩ coRP, poprawiając wynik Pratta.

Ostatecznie w 2002 r. opracowanie algorytmu AKS pokazało, że PRIMES leży w klasie P. Nie wiadomo jednak czy PRIMES jest P zupełne, czy należy do zawartych w P klas L (problemy wymagające logarytmicznego rozmiaru pamięci) lub NC (złożoność czasowa $\mathrm {O} ((\log \,n)^{k})$ na komputerze z wielomianową liczbą procesorów równolegle wykonujących obliczenia).

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Primality Test, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-03-07].