Test pierwszości

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 (2011 rok) nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.

Metoda naiwna[edytuj | edytuj kod]

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 \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 niestety 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[edytuj | edytuj kod]

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. 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 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[edytuj | edytuj kod]

Istnieje deterministyczny test pierwszości oparty o krzywe eliptyczne, działający w czasie O(log6n). 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(log4n). 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(log12n), choć w praktyce jest wolniejszy od metod probabilistycznych.

Złożoność[edytuj | edytuj kod]

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, algorytm Adlemana-Huanga zmniejszył złożoność problemu do ZPP = RPcoRP, poprawiając wynik Pratta.

Ostatecznie opracowanie algorytmu AKS pokazało, że PRIMES leży w klasie P. Nie wiadomo jednak, czy PRIMES jest P zupełne lub czy należy do zawartych w P klas L (problemy wymagające logarytmicznej pamięci) lub NC (czas O((log n)k) na komputerze z wielomianową liczbą procesorów równolegle wykonujących obliczenia).