Kilkanaście lat temu zetknąłem się z heurystyką rho Pollarda. Polega ona na obliczaniu kolejnej wartości wielomianu W[x] modulo n startujacego z ziarna a. Metoda ładnie i dostępnie opisana w wikipedii, książkach do kryptografii.
Opiszę tu swoje (alternatywne) podejście, bo jak większość moich pomysłów, ciężko jest mi je publikować.
We wszystkich tych źródłach pojawia się informacja, że wielomianem nie może być wielomian x*x-2 ani x*x.
A właśnie drugi z tych wielomianów użyłem, kiedy zacząłem testować heurystykę. Występowała niejednoznaczność, którą można było bardzo łatwo usunąć biorąc kolejną wartość wielomianu jako
f(x) = min( x^2, n-x^2 ) mod n .
Zastosowanie tego wielomianu, nie dość, że zmniejsza o połowę krotność występujacych współczyników, to jeszcze ma kilka dodatkowych własności bardzo przyspieszajacych obliczenia. Można używać indeksów dla szacowania, kiedy i gdzie może pojawić się dzielnik.
Zmienia się także warunek stopu. Nie jest już jeden:
nwd( f(a)^m, n ),
gdzie f(a)^m oznacza m-krotne złożenie f liczone w a,
czy w modyfikacji p-1: nwd( f(a)^m -1, n ) .
Odpada także przygotowanie liczby do obliczeń przez zignorowanie kilku początkowch iteracji, jakie spotkałem w jednej z książek dotyczących algorytmów.
Wybieramy ziarno 1<a<(n-1)/2. Zapamiętujemy jego wartość (dla indeksu).
Obliczamy f(a), kiedy po raz pierwszy uzyskamy wartość większą niż n, wtedy zapamiętujemy dodatkowo b jako mniejszą z reszt z dzielenia przez n: b = min( b%n, (n-b)%n ).
Powtarzamy obliczenia zliczając złożenia, aż uzyskamy wartość a, b, 0 albo 1.
W przypadku uzyskania 0 dzielnikiem jest ziarno a.
Gdy uzyskamy ciąg okresowy z wyrazem a lub b, liczymy dla tego wyrazu:
np. d=nwd( a-1,n).
Gdy 0<d<n/2, d jest dzielnikiem. Przy wartości d=0 jeszcze nic straconego. Liczymy dla pewnego elementu x =f(a)^m:
e = nwd( x, f(x) ) ,
który jest kolejnym kandydatem na dzielnik.
Najciekawszy przypadek jest wtedy, gdy cyklem jest 1. W standardowym podejściu ten przypadek powoduje błąd heurystyki. Ale nie tutaj.
Zaczynamy algorytm z ziarnem 1<a+1<(n-1)/2. I teraz tylko liczby pierwsze mogą uzyskać ciąg złożony z 1. W sprawdzanych przeze mnie przypadkach pojawia się inny ciąg stały złożony z dzielnika n. Cykle jedynek i dzielnika przeplatają się wzajemnie dla kolejnych ziaren.
Gdy nie znajdziemy dzielnika, zwiększamy ziarno o 1, oraz puszczamy algorytm jeszcze raz, pamiętając dodatkowo poprzednie wartości a, b. Teraz istotne jest ich znalezienie w nowo powstającym ciągu.
Cykl dla sąsiedniego ziarna nie musi zawierać zapamiętanych wartości. Jest wtedy rozłączny, co pozwala oszacować, czy wogóle jest miejsce na dzielniki. Czy będą związane z jakąś liczbą pierwszą, czyli gdzie ich szukać.
Kilkanaście lat temu myślałem o pamiętaniu ich w tablicy, by startować z ziarna jeszcze nie występującego.
Ale po co zapamietywać liczność cyklu? Jest on potrzebny dla oczacowania, czy mamy do czynienia z liczbą pierwszą czy złożoną. Cykl długości (n-3)/4 powtarzający się dla dwu sąsiednich (względnie pierwszych) ziaren wskazuje liczbę pierwszą.
Uwaga, ziaren równych 0, 1, n-1 nie należy brać pod uwagę, uzyska się stały ciąg trywialnej wartości.
Przykłady.
Liczba 51.
Ziarno 2, ciąg wpada w cykl [1].
Ziarno 3, ciąg wpada w cykl [18], nwd(18-1, 51) = 17, oraz 51=3*17.
Przeplatane cykle [1] oraz [18].
Liczba 35.
Ziarno 2, ciąg [2, 4, 11, 16,... ] ogon [2,4], cykl (druga z zapamiętanych wartości to 11) [11, 16], liczymy -1+11 = 10 (mod 35), d = nwd( 10, 35 ) = 5 jest dzielnikiem.
Ziarno 5, ciąg [5, 10, 5...] z cyklem [5, 10]. Teraz d=nwd(4,35)=1. Drugi warunek stopu e=nwd(5,10)=5 wskazuje dzielnik 35.
Liczba pierwsza 47.
Dla wiekszości ziaren mamy cykle długości 11 elementów, ziarno 2 ma zapamiętaną wartość 2, ziarno 3 ma cykl rozłączny (nie zawierający 2), oba cykle wybierają 22 elementy z (47-3)/2 = 22 dostępnych. Jest to liczba pierwsza.
Brak komentarzy:
Prześlij komentarz