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).