b'\n_START_ARTICLE_\nTest pierwszo\xc5\x9bci\n_START_PARAGRAPH_\nTest pierwszo\xc5\x9bci \xe2\x80\x93 algorytm okre\xc5\x9blaj\xc4\x85cy, czy dana liczba jest pierwsza, czy z\xc5\x82o\xc5\xbcona. Nie jest to r\xc3\xb3wnowa\xc5\xbcne znalezieniu jej rozk\xc5\x82adu na czynniki pierwsze. W obecnej chwili (2011 rok) nie s\xc4\x85 znane efektywne algorytmy rozk\xc5\x82adu na czynniki pierwsze, natomiast testy pierwszo\xc5\x9bci mo\xc5\xbcna przeprowadza\xc4\x87 bardzo szybko.\n_START_SECTION_\nMetoda naiwna\n_START_PARAGRAPH_\nNajprostszy test pierwszo\xc5\x9bci wygl\xc4\x85da nast\xc4\x99puj\xc4\x85co: dla danej liczby n nale\xc5\xbcy sprawdzi\xc4\x87, czy dzieli si\xc4\x99 ona kolejno przez 2, 3, a\xc5\xbc do n\xe2\x88\x921. Je\xc5\x9bli przez \xc5\xbcadn\xc4\x85 z nich si\xc4\x99 nie dzieli, oznacza to, \xc5\xbce jest pierwsza._NEWLINE_Zamiast testowa\xc4\x87 wszystkie liczby do n\xe2\x88\x921, wystarczy sprawdzi\xc4\x87 podzielno\xc5\x9b\xc4\x87 n przez liczby mniejsze lub r\xc3\xb3wne ._NEWLINE_Kolejne udoskonalenie polega na sprawdzaniu podzielno\xc5\x9bci n jedynie przez liczby pierwsze mniejsze lub r\xc3\xb3wne . Ich list\xc4\x99 \xc5\x82atwo mo\xc5\xbcemy uzyska\xc4\x87 metod\xc4\x85 sita Eratostenesa. Metoda ta wci\xc4\x85\xc5\xbc wymaga wykonania du\xc5\xbcej liczby () dziele\xc5\x84, co oznacza, \xc5\xbce ju\xc5\xbc dla 50-cyfrowych liczb pierwszych jest niewykonalna na wsp\xc3\xb3\xc5\x82czesnych komputerach.\n_START_SECTION_\nSzybkie testy deterministyczne\n_START_PARAGRAPH_\nIstnieje deterministyczny test pierwszo\xc5\x9bci oparty o krzywe eliptyczne, dzia\xc5\x82aj\xc4\x85cy w czasie . Jego dzia\xc5\x82anie opiera si\xc4\x99 jednak na pewnych dotychczas nieudowodnionych twierdzeniach z teorii liczb. Jest skomplikowany w implementacji, ale prawdopodobnie jest to najcz\xc4\x99\xc5\x9bciej u\xc5\xbcywany deterministyczny test pierwszo\xc5\x9bci._NEWLINE_Je\xc5\x9bli uog\xc3\xb3lniona hipoteza Riemanna jest prawdziwa, test Millera-Rabina mo\xc5\xbcna przekszta\xc5\x82ci\xc4\x87 w test deterministyczny, dzia\xc5\x82aj\xc4\x85cy w czasie . W praktyce jest on jednak wolniejszy od poprzedniego._NEWLINE_W 2002 roku Manindra Agrawal, Nitin Saxena i Neeraj Kayal opublikowali pierwszy deterministyczny wielomianowy test, nie opieraj\xc4\x85cy si\xc4\x99 na \xc5\xbcadnych niedowiedzionych za\xc5\x82o\xc5\xbceniach, zwany testem pierwszo\xc5\x9bci AKS. Test ten w oryginalnej wersji dzia\xc5\x82a w czasie  cho\xc4\x87 w praktyce jest wolniejszy od metod probabilistycznych.\n_START_SECTION_\nZ\xc5\x82o\xc5\xbcono\xc5\x9b\xc4\x87\n_START_PARAGRAPH_\nW teorii z\xc5\x82o\xc5\xbcono\xc5\x9bci formalnie opisuje si\xc4\x99 j\xc4\x99zyk liczb pierwszych jako PRIMES. Mo\xc5\xbcna pokaza\xc4\x87, \xc5\xbce PRIMES nale\xc5\xbcy do klasy coNP: jego dope\xc5\x82nienie COMPOSITES nale\xc5\xbcy do NP, gdy\xc5\xbc mo\xc5\xbcna \xc5\x82atwo niedeterministycznie stwierdzi\xc4\x87, \xc5\xbce jaka\xc5\x9b liczba jest z\xc5\x82o\xc5\xbcona \xe2\x80\x93 zgaduj\xc4\x85c jej dzielniki._NEWLINE_W 1975 roku, Vaughan Ronald Pratt pokaza\xc5\x82, \xc5\xbce istniej\xc4\x85 certyfikaty pierwszo\xc5\x9bci: sprawdzalne w czasie wielomianowym dowody, \xc5\xbce dana liczba jest pierwsza. Tym samym udowodni\xc5\x82, \xc5\xbce j\xc4\x99zyk PRIMES nale\xc5\xbcy te\xc5\xbc do klasy NP, a wi\xc4\x99c nale\xc5\xbcy do przeci\xc4\x99cia NP \xe2\x88\xa9 coNP._NEWLINE_Kolejne algorytmy Solovay-Strassena i Millera-Rabina umie\xc5\x9bci\xc5\x82y j\xc4\x99zyk PRIMES w klasie coRP (jego dope\xc5\x82nienie nale\xc5\xbcy do RP, czyli klasy problem\xc3\xb3w, dla kt\xc3\xb3rych istnieje probabilistyczna maszyna Turinga dzia\xc5\x82aj\xc4\x85ca w czasie wielomianowym, kt\xc3\xb3ra zwraca \xe2\x80\x9enie\xe2\x80\x9d zawsze, kiedy prawid\xc5\x82ow\xc4\x85 odpowiedzi\xc4\x85 jest \xe2\x80\x9enie\xe2\x80\x9d, i zwraca \xe2\x80\x9etak\xe2\x80\x9d (z prawdopodobie\xc5\x84stwem, kt\xc3\xb3re dla \xc5\xbcadnych danych nie spada poni\xc5\xbcej pewnej warto\xc5\x9bci) lub \xe2\x80\x9enie\xe2\x80\x9d, kiedy prawid\xc5\x82ow\xc4\x85 odpowiedzi\xc4\x85 jest \xe2\x80\x9etak\xe2\x80\x9d. W 1992 roku algorytm Adlemana-Huanga zmniejszy\xc5\x82 z\xc5\x82o\xc5\xbcono\xc5\x9b\xc4\x87 problemu do ZPP = RP \xe2\x88\xa9 coRP, poprawiaj\xc4\x85c wynik Pratta._NEWLINE_Ostatecznie w 2002 r. opracowanie algorytmu AKS pokaza\xc5\x82o, \xc5\xbce PRIMES le\xc5\xbcy w klasie P. Nie wiadomo jednak czy PRIMES jest P zupe\xc5\x82ne, czy nale\xc5\xbcy do zawartych w P klas L (problemy wymagaj\xc4\x85ce logarytmicznego rozmiaru pami\xc4\x99ci) lub NC (z\xc5\x82o\xc5\xbcono\xc5\x9b\xc4\x87 czasowa  na komputerze z wielomianow\xc4\x85 liczb\xc4\x85 procesor\xc3\xb3w r\xc3\xb3wnolegle wykonuj\xc4\x85cych obliczenia.'