W zasadzie jak na razie są tylko dwie sprawdzone metody poszukiwania dowolnych liczb pierwszych:
1). to faktoryzacja, i tu chodzi o to żeby znajdować dzielniki danej liczby inne niż ona sama i jeden. Mamy tu do wyboru kilka technik (najpopularniejszych):
- trail division, czyli dzielimy daną liczbą przez wszystkie liczby pierwsze od 2 do pierwiastka z tej liczby. Obliczenia wymagają małej ilości pamięci ale olbrzymiej ilości czasu.
- P-1, metoda opracowana przez Johna Pollarda, która bazuje na małym twierdzeniu Fermata, i opiera się na szukaniu GCD. Nie wymaga dużych ilości pamięci ale ze względu na czas obliczeń nadaje się głównie do poszukiwania relatywnie dużych dzielników, tam gdzie metoda trial division staje już zasadniczo nie użyteczna bo dzielenie trwało zbyt długo.
- ECM, czyli metoda krzywych eliptycznych (Lenstra), która w zasadzie też poszukuje GCD ale różni się metodą wyboru kandydatów.
Żadna z tych metod przy obecnym stanie techniki nie nadaje się do 100% potwierdzenia pierwszości liczby. Ponieważ metody te mogą potrzebować wielu lat na weryfikację czy bardzo duża liczba jest pierwsza. Mimo to są użyteczne w pewnym ograniczonym zakresie do odnajdywania relatywnie małych dzielników dla dużych kandydatów na liczbę pierwszą.
2). Metody sitowe, polegające na odsianiu z pewnego zbioru liczb które są lub nie są pierwsze. I tu w zasadzie mamy dwie najpopularniejsze techniki:
- sito Arastotenesa, znane chyba wszystkim ze szkoły średniej, polegająca na odrzucaniu ze zbioru liczb które są kolejnymi wielokrotnościami liczb pierwszych. Obliczenia są szybkie ale wymagają dużej ilości pamięci.
- sito Atkina, które działa na podobnej zasadzie ale wykorzystuje arytmetykę modulo. Jest szybsze niż sito Erastotenesa i wymaga mniej pamięci.
Jednakże te metody sitowe nie nadają się dla dużych liczb ponieważ wymagały by olbrzymich ilości pamięci (pojedyncze liczby zajmują megabajty a trzeba by ich przetrzymywać ogromne ilości).
Istnieją jeszcze inne metody ale nie są to metody uniwersalne. Działają dla kandydatów na liczby pierwsze pewnego typu jak np. liczby Mersenne-a, Riesela, itp.
Są też metody probabilistyczne jak np. test Millera-Rabina. Ale są z nimi dwa zasadnicze problemy:
- W zasadzie ich wyniki nie wskazują czy dana liczba jest pierwsza a bardziej czy jest złożona. Tzn. jeśli test zwraca fałsz to znaczy że liczba na pewno jest złożona, natomiast jeśli zwraca prawdę to liczba jest prawdopodobnie pierwsza.
- Testy probabilistyczne do wyboru pewnych argumentów używają wartości losowych przy czym liczby te muszą posiadać pewne określone cechy. W związku z tym z pewnym prawdopodobieństwem może się zdarzyć tak że nie uda się wylosować żadnej liczby która te warunki spełnia i program w padnie w nieskończoną pętlę (przed czym oczywiście można się zabezpieczyć ustawiając odpowiedni limit prób). Tyle że z punktu widzenia użyteczności w zasadzie wystarczy że program "będzie miał pecha" i będzie potrzebował bardzo długiego czasu na wylosowanie odpowiednich liczb żeby okazał się nieefektywny.
P.S. Np. w Mersenne@home w pre-kalkulacji wykorzystuję sito Atkina do znajdywania wszystkich liczb pierwszych do poziomu (2^64)-1, i używam ich jako dzielników do trial division. Oczywiście żeby sprawę przyśpieszyć używam także innych ułatwień wynikających z małego twierdzenia Fermata, za pomocą których udaje się jeszcze zmniejszyć liczbę dzieleń o jeden czy dwa rzędy wielkości. I dzięki temu szybko odsiewam 15-20% kandydatów.
