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 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 n1, wystarczy sprawdzić 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 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. 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 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 \Omicron(\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 \Omicron(\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 \Omicron(\log^{12} n) 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 NPcoNP.

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 = RPcoRP, 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 \Omicron((\log\, n)^k) na komputerze z wielomianową liczbą procesorów równolegle wykonujących obliczenia.

Zobacz też[edytuj | edytuj kod]