Heurystyka rozkładu na czynniki pierwsze

Heurystyki rozkładu liczb złożonych służą do szybkiego znajdowania dzielników pierwszych dużych liczb naturalnych. Mając daną liczbę N próbują zwrócić jej dzielnik q. Spotkałem test Rabina-Millera do sprawdzania, czy liczba jest pierwsza. Algorytm ten stał się punktem wyjścia do opracowania metody, która okazała się bardzo podobna do heurystyki ro Pollarda, przynajmniej w interpretacji graficznej.

Z algorytmu faktoryzacji ro Pollarda wziąłem część oznaczeń:
http://pl.wikipedia.org/wiki/Algorytm_faktoryzacji_rho_Pollarda

Oryginalny test Rabina-Millera jest tu:
http://pl.wikipedia.org/wiki/Test_Millera-Rabina

Algorytm znalezienia rozkładu liczby pierwszej N na czynniki.
1.Wyłączam z liczby N wielokrotności 2, by otrzymać liczbę nieparzystą
2.Ustalam ziarno – liczbę z zakresu {2, ..., (N-1)/2}
3.Obliczam
z_{i+1} = min {z_i^2 mod N, -z_i^2 mod N}
dopóki nie uzyskam 0, 1, albo powstanie cykl a_i
4.Gdy z=1 algorytm zawodzi, należy wrócić do 3 z nowym ziarnem
5.Gdy istnieje cykl (a_i), obliczane jest b=nwd(a, N) dla dowolnego elementu a cyklu, wtedy b jest dzielnikiem N, jeśli b=1, należy wrócić do 3 wybierając nowe ziarno nie należące do cyklu
6.Gdy z=0, ziarno jest dzielnikiem N
7.Jeśli po przejrzeniu wszystkich ziaren z zakresu otrzymywane są cykle z nwd(a,N)=1 albo ciągi jedynek (1), liczba N jest pierwsza

Jako jeden z pierwszych kroków można przeprowadzić pierwszy fragment testu pierwszości Rabina-Millera. Wynik pozytywny dla co najmniej dwu ziaren pozwala pominąć szukanie dzielników liczby pierwszej. Wykorzystanie ziarna inicjowanego a^m zamiast a powoduje skrócenie ogona, dzięki czemu cykl jest szybciej uzyskiwany. Następuje zmniejszenie krotności wartości występujących w cyklach,.

Ze względu na symetrie ziarna z oraz N-z dają te same wartości, przy czym dla N-1 od pierwszej iteracji otrzymywane są same jedynki.

Przykład 1: liczba złożona 57 = 3*19
Liczba 57-1 = 56 = 2^3*7. Spodziewane są zatem cykle zaczynające się nie dalej niż w 3 iteracji. Jeżeli ziarna inicjujemy nie przez z^7, lecz przez z, wyniki dają cykle przesunięte.
Ziarno z=2 daje wartości 14 (2^7 mod 57), 25 (14^2 mod 57), 2 (-(25^2) mod 57), 4, 16, 28, 14 (-28^2 mod 57), czyli okres 6 od pierwszej pozycji. Wspólny dzielnik nwd(2,57)=1, zmieniamy ziarno.
Ziarno z=3 daje kolejno wartości: 21, 15, 3, 9, 24, 6, 21, okres taki sam od pierwszej pozycji, nwd(3,57) = 3 jest jednym z dzielników liczby początkowej.
Dla innych ziaren okresy wynoszą odpowiednio 7: (7,8), 12: (12,27), 18: (18), 19:(19), występuje także 20: (1)!

Przykład 2: liczba złożona 49 = 7^2
Ponieważ 48 = 2^4*3, spodziewane są cykle zaczynające się nie dalej niż od 4.tej iteracji. Występują następujące cykle: (0), (1), (6,13,22), (8,15,20). Dla ziarna z=18 uzyskiwana jest 1 sugerująca, że liczba jest pierwsza!
Kiedy z nie jest inicjowane potęgą z^3, pojawiają się dodatkowe cykle długości 6, np. (2,4,16,11,23,10). Wtedy z ziarnem 18 nie ma kłopotu, tworzy się cykl (18,19).

Przykład 3: liczba pierwsza 53
Rozkład 52=2^2*13.
Występują 2 cykle: (1) oraz (4,16,9,25,11,15,13,10,6,17,24,7).
Kiedy z nie jest inicjowane potęgą, cykl 12-wyrazowy występuje dla większości ziaren.