Algorytm sprawdzający pierwszość liczby

Treść tego programu zawarta jest w dodatku B. Służy on do sprawdzania czy liczba podana jako parametr wejściowy jest pierwsza. W przypadku gdy tak nie jest, dodatkowo są obliczane niektóre jej dzielniki (co najmniej jeden). Większa część programu jest implementacją częściowej arytmetyki dużych liczb (jedynie kilka potrzebnych operacji). W postaci przedstawionej w tej pracy można operować na liczbach rzędu do (132 cyfry dziesiętne). Zasada działania algorytmu polega na sekwencyjnym przeszukiwaniu przestrzeni możliwych rozwiązań i sprawdzaniu czy dana liczba jest dzielnikiem liczby sprawdzanej. Ponieważ dysponujemy wieloma procesorami, oczywistą rzeczą jest podzielenie przestrzeni na części i przydzielenie przeszukiwania każdej z nich innemu procesorowi wirtualnemu. Dodatkowe przyspieszenie obliczeń można uzyskać przez zawężenie przeszukiwanej przestrzeni. Jeśli dana jest liczba x, to wystarczy sprawdzać liczby mniejsze od . Ponieważ obliczenie pierwiastka (nawet przybliżone) jest czasochłonne, dla danych większych od niniejszy program sprawdza liczby mniejsze od , czyli trochę więcej od (dla liczb mniejszych od jest to ciągle ). Fakt, że nie trzeba sprawdzać podzielności przez liczby parzyste jeśli liczba nie jest parzysta, pozwala na na dalsze skrócenie czas obliczeń (jeśli liczba jest parzysta, to w czasie stałym można stwierdzić, że jest złożona).

W przypadku, gdy liczba jest pierwsza, nastąpi przejrzenie wszystkich liczb z odpowiedniego zakresu. Jeśli dysponujemy N procesorami wirtualnymi, to dla liczby x algorytm wykona się w krokach (liczba obrotów pętli w funkcji testuj).

Samo sprawdzanie czy liczba jest pierwsza można wykonać za pomocą testu Millera-Rabina ([9], strona 940). Algorytm ten jest jednak algorytmem probabilistycznym i z pewnym prawdopodobieństwem podaje złe wyniki. Ponadto w żaden sposób nie otrzymamy za jego pomocą czynników rozkładu sprawdzanej liczby. Rozkład na czynniki można przeprowadzić na przykład za pomocą heurystyki Pollarda przedstawionej w tej samej książce ([9], strona 947). Jeśli p jest niewielkim czynnikiem n, to za pomocą heurystyki można go znaleźć średnio po krokach, a do rozłożenia liczby n na czynniki potrzeba co najwyżej operacji arytmetycznych. Jednak także nie ma gwarancji ani czasu działania, ani tego, że zakończy się sukcesem. Dodatkowo heurystykę tą należałoby połączyć z jakimś testem sprawdzającym czy liczba jest pierwsza, czy złożona (na przykład test Millera-Rabina wspomniany wyżej).