Algorytm we wcześniejszym poście wymagał znalezienia pierwiastka kwadratowego z liczby, liczonego dwukrotnie podczas inicjacji.
Publikowałem już sposób na liczenie pierwiastka rok temu, w listopadzie 2012 roku, lecz teraz znalazłem nieco szybszą technikę.
Ustalmy liczbę n oraz drugą liczbę p położoną między pierwiastkiem sześciennym oraz kwadratowym z n. Nic więcej o liczbie p nie potrzeba wiedzieć, jest ona pierwszym przybliżeniem pierwiastka. Resztę załatwią konwersje, a być może także wzór skróconego mnożenia.
Dzielimy n z resztą przez p (dwukrotnie), by uzyskać postać
n = (a*p+b)*p+c (1)
Jest to zapis liczby trójcyfrowej.
Możemy sprawdzić, czy a, b, c stanowią współczynniki trójmianu kwadratowego d^2+2de+e^2+f, jeśli tak, pierwiastek można przybliżyć przez
(dp+e)^2+f.
Jeśli jednak b>2de, też możemy posłużyć się wzorem, do którego należy dodać poprawkę (b-2de)*p. Sposób też prowadzi do celu, lecz jest znacznie dłuższy. Zbieżność do pierwiastka jest wolniejsza.
Zatem pierwsza faza, sprowadzamy a do postaci podzielnej przez 4, b do liczby parzystej za pomocą formuł:
a-1 AND b+=p; b-1 AND c+=p. (2)
Np. mając (a,b,c) = (5, 4, 34) dla p=125 uzyskujemy z pomocą formuł (2)
(a,b,c) = (5-1, 4+125, 34) = (4, 129, 34) = (4, 129-1, 34+125) = (4, 128, 159)
Korzystamy z konwersji podwajania systemu
(a,b,c)_p = (a/4, b/2, c)_(2p) (3)
czyli w przykładzie mamy (a,b,c) = (1, 64, 159)_250 .
Kiedy już a<4, oraz nie dopasujemy wzoru skróconego mnożenia, dążymy do zmniejszenia b. W odróżnieniu od zeszłorocznego algorytmu najlepiej to zrobić za pomocą konwersji o floor(a*b/3). Konwersja ta zmniejsza b o co najmniej połowę, może także zmniejszyć a. Branie połowy (a*b/2) może doprowadzić do zmniejszenie b do wartości ujemnej, zaś chcemy zachować a=1 jako niezmiennik, oraz wartość liczby trójcyfrowej powinna pozostać większa niż pierwiastek kwadratowy.
Przykład dla n=8934053
Przyjmijmy p=1000, wtedy (a,b,c) = (8, 934, 53)_1000
Pierwsza konwersja (3) sprowadza do (a,b,c) = (2, 467, 53)_2000
konwersja o floor(a*b/3) = 311
2 467 53
2 467-2*311
2-1 2156 53 // dodaję do b (2000+311) = 2311
1 2156-311 53-2156*311
1 1845-291 -670463 // dodaję do c 291*p
1 1554 2038
oraz (a,b,c) = (1, 1554, 2038)_2311
konwersja o floor(a*b/3) = 518, nowa podstawa p = 2311+518 = 2829
1 1554 2038
1 1554-518
1 1036 2038
1 518 2038-1036*518 // dodajemy do c 189*p
1 518-189 -534610
1 329 71
konwersja o floor(a*b/3) = 109, nowa podstawa p = 2829+109 = 2938
1 329 71
1 329-109
1 220 71
1 220-109 71-220*109
1 111-9 -23909 // dodajamy do c 9*p
1 102 2533
Sprawdzamy wzór skróconego mnożenia (1+51)^2 = 1+102+2601 oraz porównujemy. Niezgodność na pozycji c, jest za dużo o 68. Ale jest dobrze.
Zatem (a,b,c)_p = (1*p+51)^2-68 = (2938+51)^2-68 = 2989^2-68.
Zmniejszamy kwadrat
2989^2-68 = 2988^2+5976+1-68 = 2988^2+5909.
Znaleziony został pierwiastek całkowitoliczbowy 2988 oraz reszty: 5909 z niedomiarem, 68 z nadmiarem.
Dokładniejszą wartość pierwiastka mozna policzyć za pomocą interpolacji 2988 + 5909/(5909+68) = 2988,988623; dokładniejsza wartość 2988,9886249365352845723814
Błąd dopiero na szóstej pozycji po przecinku.
28 listopada 2013
25 listopada 2013
Różnica kwadratów w faktoryzacji
Przedstawienie liczby rozkładanej n w postaci dwu kwadratów leży u podstaw jednych z najszybszych metod faktoryzacji. Są to np. metoda sita kwadratowego, sita ciał liczbowych, a nawet ułamków łańcuchowych.
Wykorzystują one kongruencję Legendre'a
x*x = y*y (mod n) ,
gdzie wartości są dodatnie, x<y<n oraz x+y nie sumuje się do n.
Sposób stosowania tej kongruencji znajduje się w "Teorii liczb w informatyce" Song Y. Yana.
Teraz jednak chcę przedstawić inny algorytm, w którym wykorzystuję jedną z najbardziej prostych konwersji systemów niedziesiątkowych, a zarazem wzór skróconego mnożenia:
p^2 + 2*p + 1 = (p+1)^2 + 0*p + 0 = (p+1)^2 (1) .
Kiedy przedstawię liczbę n w postaci:
n = a*a - b*b - c , (2)
gdzie a jest najmniejsze możliwe a^2 < n < (a+1)^2, b jest największe możliwe. Wartość b^2+c można uzyskać wieloma sposobami, ale nie udało mi się jej zmniejszyć.
Przyrost między kolejnymi kwadratami p^2 oraz (p+1)^2 jest równy 2*p+1.
Dodając to do wyrażeń a^2, b^2+c ich różnica pozostanie równa n.
Po zwiększeniu c można dalej zwiększać b, co prowadzi do następującego algorytmu, który zatrzymuje się gdy c=0. Wtedy dzielnikami są:
n = a^2 - b^2 = (a+b)*(a-b) .
Drugim wyjściem jest zwiększenie b powyżej pierwiastka z n, co świadczy o braku dzielników.
inicjacja: a=deck(sqrt(n)); c=a^2-n; b=floor(sqrt(c)); c=c-b^2;
k=a; // kopia dla ograniczenia zakresu
while ( b<k ) {
a++;
c+=2*a+1; // dodanie niedomiaru od najbliższego większego kwadratu
while( 1 ) {
d = 2*b+1; // by nie liczyć dwukrotnie niedomiaru do kwadratu b
if( c<d ) break;
else { c-=d; b++; } // b wzrasta do kolejnego kwadratu kosztem c
if( 0==c ) return text("dzielniki: ", a-b, a+b);
}
}
return text("n jest pierwsza");
Funkcja text() wypisuje swoje argumenty na wyjściu. Pierwiastek z n powoli wzrasta po kolejnych kwadratach. Zaś b^2+c przyrastajace o tę samą wartość modyfikuje się do największego możliwego dla tej wartości kwadratu.
Ze wzrostem b spada liczność obliczeń w pętli wewnętrznej.
Złożoność.
Jeśli przyjmiemy, że pętla wewnętrzna wykona się dokładnie raz, pogorszymy złożoność. Jest to spowodowane tym, że przy każdym, nawet fikcyjnym zwiększeniu a bedziemy zwiększać b, zaś istotniejsze są zwiększenia b. Wyrażenia d=2*b+1 wykonują się w czasie liniowym, pozostałe przekształcenia to czas praktycznie stały. Pętla zewnętrzna wykona się nie więcej niż pierwiastek z n razy, zwiększając b o 1 w każdym kroku. Praktycznie mniej, gdyż b może nie być bardzo małe. Dodatkowo, w pierszych iteracjach zwiększanie b odbywa się bardzo szybko, zwalniając w czasie przebiegu do 1-2 zwiększeń b na jedno zwiększenie a. Podsumowując, złożoność tego algorytmu nie przekracza
O( n sqrt(n) ) dla pamięci,
max{ O( sqrt(n) ), O( sqrt ) } dla operacji.
Dla 18703 mamy wartości początkowe a=137, b^2+c = 66, zatem b=8, c=2.
Jest to złośliwy przypadek, gdyż dzielniki są dosyć odległe, zostaną znalezione dopiero gdy b=129, czyli w 51 na 56 iteracji. Podczas każdej iteracji pętli zewnętrznej wartość b zwiększała się od 1 do 8, najczęściej 2 lub 3.
W następnym kroku mamy:
a=138, jest dodane 2*137+1 = 275;
od c = 2+275 = 277 odejmujemy 2*8+1= 17 (wtedy b=9)
2*9+1 = 19 (oraz b=10)
2*10+1 = 21 (oraz b=11)
jeszcze parę razy i otrzymamy c=17 przy b=18,
Mamy do czynienia z wyrażeniem 138^2 - (18^2+17) = 19044 - 341 = 18703.
W kolejnej iteracji dodamy 2*138+1 = 277. Będziemy zabierać 37, 39, itd. dopóki b=24.
Wartości dodawane i zabierane tworzą proste ciągi arytmetyczne.
Algorytm dla liczb postaci n = p*q, gdzie p i q są pierwsze ma dodatkową własność. Wartość 2*b wskazuje minimalną odległość między tymi dzielnikami.
Wykorzystują one kongruencję Legendre'a
x*x = y*y (mod n) ,
gdzie wartości są dodatnie, x<y<n oraz x+y nie sumuje się do n.
Sposób stosowania tej kongruencji znajduje się w "Teorii liczb w informatyce" Song Y. Yana.
Teraz jednak chcę przedstawić inny algorytm, w którym wykorzystuję jedną z najbardziej prostych konwersji systemów niedziesiątkowych, a zarazem wzór skróconego mnożenia:
p^2 + 2*p + 1 = (p+1)^2 + 0*p + 0 = (p+1)^2 (1) .
Kiedy przedstawię liczbę n w postaci:
n = a*a - b*b - c , (2)
gdzie a jest najmniejsze możliwe a^2 < n < (a+1)^2, b jest największe możliwe. Wartość b^2+c można uzyskać wieloma sposobami, ale nie udało mi się jej zmniejszyć.
Przyrost między kolejnymi kwadratami p^2 oraz (p+1)^2 jest równy 2*p+1.
Dodając to do wyrażeń a^2, b^2+c ich różnica pozostanie równa n.
Po zwiększeniu c można dalej zwiększać b, co prowadzi do następującego algorytmu, który zatrzymuje się gdy c=0. Wtedy dzielnikami są:
n = a^2 - b^2 = (a+b)*(a-b) .
Drugim wyjściem jest zwiększenie b powyżej pierwiastka z n, co świadczy o braku dzielników.
inicjacja: a=deck(sqrt(n)); c=a^2-n; b=floor(sqrt(c)); c=c-b^2;
k=a; // kopia dla ograniczenia zakresu
while ( b<k ) {
a++;
c+=2*a+1; // dodanie niedomiaru od najbliższego większego kwadratu
while( 1 ) {
d = 2*b+1; // by nie liczyć dwukrotnie niedomiaru do kwadratu b
if( c<d ) break;
else { c-=d; b++; } // b wzrasta do kolejnego kwadratu kosztem c
if( 0==c ) return text("dzielniki: ", a-b, a+b);
}
}
return text("n jest pierwsza");
Funkcja text() wypisuje swoje argumenty na wyjściu. Pierwiastek z n powoli wzrasta po kolejnych kwadratach. Zaś b^2+c przyrastajace o tę samą wartość modyfikuje się do największego możliwego dla tej wartości kwadratu.
Ze wzrostem b spada liczność obliczeń w pętli wewnętrznej.
Złożoność.
Jeśli przyjmiemy, że pętla wewnętrzna wykona się dokładnie raz, pogorszymy złożoność. Jest to spowodowane tym, że przy każdym, nawet fikcyjnym zwiększeniu a bedziemy zwiększać b, zaś istotniejsze są zwiększenia b. Wyrażenia d=2*b+1 wykonują się w czasie liniowym, pozostałe przekształcenia to czas praktycznie stały. Pętla zewnętrzna wykona się nie więcej niż pierwiastek z n razy, zwiększając b o 1 w każdym kroku. Praktycznie mniej, gdyż b może nie być bardzo małe. Dodatkowo, w pierszych iteracjach zwiększanie b odbywa się bardzo szybko, zwalniając w czasie przebiegu do 1-2 zwiększeń b na jedno zwiększenie a. Podsumowując, złożoność tego algorytmu nie przekracza
O( n sqrt(n) ) dla pamięci,
max{ O( sqrt(n) ), O( sqrt ) } dla operacji.
Dla 18703 mamy wartości początkowe a=137, b^2+c = 66, zatem b=8, c=2.
Jest to złośliwy przypadek, gdyż dzielniki są dosyć odległe, zostaną znalezione dopiero gdy b=129, czyli w 51 na 56 iteracji. Podczas każdej iteracji pętli zewnętrznej wartość b zwiększała się od 1 do 8, najczęściej 2 lub 3.
W następnym kroku mamy:
a=138, jest dodane 2*137+1 = 275;
od c = 2+275 = 277 odejmujemy 2*8+1= 17 (wtedy b=9)
2*9+1 = 19 (oraz b=10)
2*10+1 = 21 (oraz b=11)
jeszcze parę razy i otrzymamy c=17 przy b=18,
Mamy do czynienia z wyrażeniem 138^2 - (18^2+17) = 19044 - 341 = 18703.
W kolejnej iteracji dodamy 2*138+1 = 277. Będziemy zabierać 37, 39, itd. dopóki b=24.
Wartości dodawane i zabierane tworzą proste ciągi arytmetyczne.
Algorytm dla liczb postaci n = p*q, gdzie p i q są pierwsze ma dodatkową własność. Wartość 2*b wskazuje minimalną odległość między tymi dzielnikami.
21 listopada 2013
Wariacja faktoryzacja przez proste dzielenie
Rozkład liczby n na czynniki za pomocą prostego dzielenia polega na kolejnym wstawianiu do ilorazu n/b kolejnych, najlepiej pierwszych, ewentualnie nieparzystych, liczb b. Reszta równa 0 oznacza, że b jest dzielnikiem.
Dla dużych liczb n b też jest duże, chociaż mniejsze niż pierwiastek z n. Wtedy dzielenie jest uciążliwe.
Istnieje sposób, by zmniejszyć argumenty dzielenia, by nie dzielić n/b, lecz jakieś c/b, gdzie c<n. A nawet dwa sposoby.
Pierwszy korzysta z przedstawienia liczby n jako 'liczby dwycyfrowej' jakiegoś systemu liczenia o dużej podstawie, oraz konwersje pozwalają na znajdowanie reszt - niestety, metoda wymaga liczenia ilorazów dla kolejnych liczb naturalnych przy zmniejszaniu dzielnej.
Metoda, którą opiszę dalej, pozwala przeskakiwać liczby parzyste. Zatem tworzymy ilorazy c/b, gdzie c jest nieparzyste, mniejsze od n.
Zapiszmy liczbę n w postaci wyrażenia:
n = a*b + c (1)
będziemy przekształcać wartości a, b, oraz c w taki sposób, by podczas przekształceń a tworzyło ciąg nierosnący, b było ciągiem rosnącym po wartościach nieparzystych, zaś c tworzyło ciąg przedziałami monotoniczny.
Algorytm jest rozgałęziony, a jego ogólny schemat wygląda następująco:
inicjacja: a = floor(n/3), b=3, c=n%3.
pętla dopóki a>b
czy b dzieli c (warunek 0 = c%b)? jeśli tak, b jest dzielnikiem, wyjście;
b = b+2;
rozgałęzienie, jeśli c<2a
c = c + (a%b)*(b-2);
a = b*floor(a/b) - 2*floor(a/b);
w przeciwnym razie (c>2a)
c = c-2a;
koniec pętli
Pierwsza część rozgałęzienia jest całkowito-liczbową operacją a*(b-2)/b, która zwiększa c oraz zmniejsza a. Mamy tu dodatkowo jedno dzielenie oraz mnożenie, co komplikuje algorytm. Można je przekształcić, by dzielić przez b oraz odjąć podwojony iloraz od a.
Z kolei druga część rozgałęzienia jest zwykłym odejmowaniem.
W początkowej fazie algorytmu przeważa pierwsza część, z dodatkowymi działaniami. Wykonują się jednak one na małych wartościach, dużo mniejszych niż pierwiastek z n. Pod koniec algorytmu najgorszym kawałkiem jest mnożenie (a%b)*(b-2), którego wartość może być stosunkowo blisko n. Zwiększa ona c do bardzo dużych wartości, umożliwiając stosowanie drugiej, prostszej odnogi.
Już po sprawdzeniu około 20% przypadków na możliwe wartości b do głosu dochodzi druga część rozgałęzienia, zaś przy 30% praktycznie dominuje.
Cały czas należy sprawdzać podzielność c przez b. Chociaż c (zwłaszcza przy dominacji drugiej odnogi) szybko maleje nawet do wartości bliskich b.
Fragment przykładu numerycznego, liczba 8 934 053 = 1087 * 8219.
inicjacja: a*b+c = 2 978 017 * 3 + 2
b = 3+2 = 5;
pierwsza odnoga: 2 978 017 - 2 = 2 978 015, bo 2 978 017 % 5 = 2,
c = 2 + 2*3 = 8
zmniejszanie a: 2 978 015 * 3 / 5 = 2 978 015 - 2*(595 603) = 1 786 809
nieco dalej:
a = 122 049; b = 73; c = 24 476;
sprawdzamy c%b = 21, nie jest zerem; pierwsza odnoga
b=75; reszta a%b = 24
c = 24 476 + 24*(75-2) = 26 228;
a = (122 049 - 24) - 2*(122 049 - 24)/75 = 118 771
jeszcze dalej:
a = 69 125; b = 127; c = 155 178;
sprawdzamy c%b = 111, druga odnoga
b = 129;
c = 155 178 - 2 * 69 125 = 16 928;
możemy znów sprawdzać c%b = 16 928 % 129
dla b>400 co parę przekształceń mamy kilka iteracji odnogą drugą, zaś blisko końca algorytmu mamy
a = 8685; b = 1027; c = 14 558;
sprawdzamy c%b = 180; pierwsza odnoga
b = 1029;
c = c + 453*1027 = 479 789;
a = (a-453) - 2*(a-453)/1029 = 8232-16 = 8216;
Teraz przez 29 iteracji powtarza się odejmowanie w drugiej odnodze, zanim znów zastosujemy pierwszą.
Zakończenie algorytmu
a*b+c = 8216 * 1087 + 3261, oraz 3261 = 3*1087.
Algorytm nie jest zbyt dobry. Może być nawet gorszy niż zwykłe dzielenia. Może być traktowany jako ciekawostka.
Dla dużych liczb n b też jest duże, chociaż mniejsze niż pierwiastek z n. Wtedy dzielenie jest uciążliwe.
Istnieje sposób, by zmniejszyć argumenty dzielenia, by nie dzielić n/b, lecz jakieś c/b, gdzie c<n. A nawet dwa sposoby.
Pierwszy korzysta z przedstawienia liczby n jako 'liczby dwycyfrowej' jakiegoś systemu liczenia o dużej podstawie, oraz konwersje pozwalają na znajdowanie reszt - niestety, metoda wymaga liczenia ilorazów dla kolejnych liczb naturalnych przy zmniejszaniu dzielnej.
Metoda, którą opiszę dalej, pozwala przeskakiwać liczby parzyste. Zatem tworzymy ilorazy c/b, gdzie c jest nieparzyste, mniejsze od n.
Zapiszmy liczbę n w postaci wyrażenia:
n = a*b + c (1)
będziemy przekształcać wartości a, b, oraz c w taki sposób, by podczas przekształceń a tworzyło ciąg nierosnący, b było ciągiem rosnącym po wartościach nieparzystych, zaś c tworzyło ciąg przedziałami monotoniczny.
Algorytm jest rozgałęziony, a jego ogólny schemat wygląda następująco:
inicjacja: a = floor(n/3), b=3, c=n%3.
pętla dopóki a>b
czy b dzieli c (warunek 0 = c%b)? jeśli tak, b jest dzielnikiem, wyjście;
b = b+2;
rozgałęzienie, jeśli c<2a
c = c + (a%b)*(b-2);
a = b*floor(a/b) - 2*floor(a/b);
w przeciwnym razie (c>2a)
c = c-2a;
koniec pętli
Pierwsza część rozgałęzienia jest całkowito-liczbową operacją a*(b-2)/b, która zwiększa c oraz zmniejsza a. Mamy tu dodatkowo jedno dzielenie oraz mnożenie, co komplikuje algorytm. Można je przekształcić, by dzielić przez b oraz odjąć podwojony iloraz od a.
Z kolei druga część rozgałęzienia jest zwykłym odejmowaniem.
W początkowej fazie algorytmu przeważa pierwsza część, z dodatkowymi działaniami. Wykonują się jednak one na małych wartościach, dużo mniejszych niż pierwiastek z n. Pod koniec algorytmu najgorszym kawałkiem jest mnożenie (a%b)*(b-2), którego wartość może być stosunkowo blisko n. Zwiększa ona c do bardzo dużych wartości, umożliwiając stosowanie drugiej, prostszej odnogi.
Już po sprawdzeniu około 20% przypadków na możliwe wartości b do głosu dochodzi druga część rozgałęzienia, zaś przy 30% praktycznie dominuje.
Cały czas należy sprawdzać podzielność c przez b. Chociaż c (zwłaszcza przy dominacji drugiej odnogi) szybko maleje nawet do wartości bliskich b.
Fragment przykładu numerycznego, liczba 8 934 053 = 1087 * 8219.
inicjacja: a*b+c = 2 978 017 * 3 + 2
b = 3+2 = 5;
pierwsza odnoga: 2 978 017 - 2 = 2 978 015, bo 2 978 017 % 5 = 2,
c = 2 + 2*3 = 8
zmniejszanie a: 2 978 015 * 3 / 5 = 2 978 015 - 2*(595 603) = 1 786 809
nieco dalej:
a = 122 049; b = 73; c = 24 476;
sprawdzamy c%b = 21, nie jest zerem; pierwsza odnoga
b=75; reszta a%b = 24
c = 24 476 + 24*(75-2) = 26 228;
a = (122 049 - 24) - 2*(122 049 - 24)/75 = 118 771
jeszcze dalej:
a = 69 125; b = 127; c = 155 178;
sprawdzamy c%b = 111, druga odnoga
b = 129;
c = 155 178 - 2 * 69 125 = 16 928;
możemy znów sprawdzać c%b = 16 928 % 129
dla b>400 co parę przekształceń mamy kilka iteracji odnogą drugą, zaś blisko końca algorytmu mamy
a = 8685; b = 1027; c = 14 558;
sprawdzamy c%b = 180; pierwsza odnoga
b = 1029;
c = c + 453*1027 = 479 789;
a = (a-453) - 2*(a-453)/1029 = 8232-16 = 8216;
Teraz przez 29 iteracji powtarza się odejmowanie w drugiej odnodze, zanim znów zastosujemy pierwszą.
Zakończenie algorytmu
a*b+c = 8216 * 1087 + 3261, oraz 3261 = 3*1087.
Algorytm nie jest zbyt dobry. Może być nawet gorszy niż zwykłe dzielenia. Może być traktowany jako ciekawostka.
08 listopada 2013
Modyfikacja heurystyki rho Pollarda
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.
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.
04 listopada 2013
Faktoryzacja a system Fibonacciego
Liczby Fibonacciego tworzone są wzorem rekurencyjnym:
F[0]=0, F[1], F[n+2] = F[n+1]+F[n]
W wikipedii opisano system Fibonacciego, w którym w definicji systemu o cyfrach a[i] oraz podstawach p[i]
suma_{-1<i} a[i]*p[i]
przyjęto
p[i] = F[i-2], 1<i, a[i] in {0,1}.
Dodawanie i odejmowanie w tym systemie jest proste, mnożenie i dzielenie koszmarne - lepiej się trzymać z daleka. Dla usunięcia niejednoznaczności wprowadzono formułę łączącą w okienku kolejne trzy cyfry systemu Fibonacciego:
[0,1,1]_F = [1,0,0]_F (1) .
Nie musimy mieć cyfr równych tylko {0,1}. Możemy czasowo pozwolić sobie na dowolne 'cyfry' całkowite, a wtedy mnożenie i dzielenie nieco się ułatwi.
Przykład. Liczba [3,0,0,0,0,0]_F = 3*F[7] = 3*13 = 39.
Własność (1) można wykorzystać do faktoryzacji. Sprawdziłem trzy metody przekształcania liczby n na postać p*F[m].
Idea jest następująca, stosując prawa działające na liczbach Fibonacciego tworzę ciąg 'cyfr' ze zbioru {0,p}, do pozycji F[0] dodaję ewentualną resztę całkowitą r.
1) Liczba nieparzysta p zapisana liczbą Fibonacciego F jako p*F (użyta gramatyka (p|0)*r ), gdzie p*p<n<p*p+2.
zmniejszamy p = p-2.
Przechodzimy rekursywnie modyfikując 3-cyfrowe okienko [p+a,b,c] = [p,a+b,a+c] lub [a,b,c] = [0,a+b,a+c], a<p.
Okienko przesuwamy w kierunku 'cyfr' mniej znaczących. Kiedy się nie da, dla okienka [a,b,c] stosujemy przekształcenie d=2*b+c+r oraz wypełniamy: [a, d%(2*p), e*p+r'], gdzie r' jest nową resztą d%p, e in {0,1} jest dopasowane, by nie zmienić wartości liczby.
Przykład p=21, w ostatnim okienku mamy [21, 34, 4] = [21,0,72] = [21,21,21+9].
Teraz należy 'naprawić' liczbę Fibonacciego, wracamy z okienkiem posługując się uogólnieniem okienka (1) postaci:
[0,p,p] = [p,0,0] (2) .
Wielokrotnie to stosując (czasem z nawrotami dla ostatnich cyfr) uzyskamy nową wartość
(p+2)*F +r = p*F'+r'.
Kontynuując ze zmniejszajacym się nieparzystym p znajdziemy dzielnik lub dojdziemy do standardowej liczby Fibonacciego dla n. Wtedy kończymy.
W każdej iteracji wartość p się zmniejsza, F zwiększa. Za wyjątkiem obróbki końcowej cyfry mamy do czynienia tylko z dodawaniem, odejmowaniem i porównywaniem liczb nie większych niż pierwiastek z n.
2) Jest to algorytm dla liczb F mniejszych niż pierwiastek, wykorzystujący dzielenie. W pierwszym kroku dzielimy p=n/3, uzyskując postać [p,0]+r = p*10_F+r. Sprawdzamy, czy r=p albo r=0, wtedy kończymy mając dzielnik p.
W następnym kroku sprawdzamy, o ile możemy zmniejszyć 'cyfry' p za pomocą dzielenia: p/(F+1) <= x, dla nieparzystego p przyjmujemy za x najbliższą parzystą większą niż iloraz. W następnym kroku odejmujemy p=p-x, co zwiększy nam resztę r o x*F. Podobnie jak w 1), 'naprawiamy' liczbę za pomocą (2).
Porównujemy p z r oraz zmniejszamy p = p-2. Kończymy, gdy p stanie się mniejsze niż liczba Fibonacciego F lub znajdziemy dzielnik p.
Liczba Fibonacciego się zwiększa do długości osiągniętej przy pierwiastku z n, wartości p początkowo bardzo szybko maleją, póżniej słabiej, bo ilorazy dążą do 1, iloraz (całkowity) równy 0 oznacza, że p<F.
3) Jest odwróceniem algorytmu 1). Startujemy z liczby Fibonacciego dla wartości n oraz usiłujemy doprowadzić pierwszą 'cyfrę' okienka do wartości p albo do 0. Należy odpowiednio reagować, gdyż wartości w okienku mają silną tendencję do tworzenia ciągów rozbieżnych. Teraz wygodniej jest czasami nadawać 'cyfrom' wartości ujemne i czasami zciągać cyfrę z już ustalonej pozycji.
Zwiększamy p o 2. Są kłopoty z ustaleniem kryterium stopu, gdyż sprawdzanie, czy p<F za każdym zwiększeniem p jest bezcelowe. Z kolei konieczność 'naprawy' liczby po dotarciu okienka do cyfry najmniej znaczącej zachodzi stosunkowo rzadko.
Przykładowy fragment działania na okienku dla p=67: [65,0,65]=[67,-2,63]; przesunięcie [-2,63,0]=[0,61,-2]; przesunięcie [61,-2,0]=[0,59,61] itd.
Następuje zciąganie liczby Fibonacciego do krótszego ciągu. Operujemy na wzrastajacych wartościach dodawaniem, odejmowaniem i porównywaniem. Osiągniemy pierwiastek z n tylko dla liczb pierwszych.
Liczba w systemie Fibonacciego jest długa, dochodzi do 5 log n, ale przekształcenia i pętle (może z wyjątkiem napraw) są liniowe. Wszystkie przedstawione algorytmy mają porównywalną krotność przypadków do sprawdzenia. Bo albo p się zmienia, albo F.
Są to kolejni kandydaci na wielomianowe algorytmy faktoryzacji, gdyż znalezienie wartości cyfry liczby Fibonacciego można wykonać w czasie logarytmicznym.
Algorytm 1) sprawdza najpierw duże dzielniki, pozostałe najpierw małe.
F[0]=0, F[1], F[n+2] = F[n+1]+F[n]
W wikipedii opisano system Fibonacciego, w którym w definicji systemu o cyfrach a[i] oraz podstawach p[i]
suma_{-1<i} a[i]*p[i]
przyjęto
p[i] = F[i-2], 1<i, a[i] in {0,1}.
Dodawanie i odejmowanie w tym systemie jest proste, mnożenie i dzielenie koszmarne - lepiej się trzymać z daleka. Dla usunięcia niejednoznaczności wprowadzono formułę łączącą w okienku kolejne trzy cyfry systemu Fibonacciego:
[0,1,1]_F = [1,0,0]_F (1) .
Nie musimy mieć cyfr równych tylko {0,1}. Możemy czasowo pozwolić sobie na dowolne 'cyfry' całkowite, a wtedy mnożenie i dzielenie nieco się ułatwi.
Przykład. Liczba [3,0,0,0,0,0]_F = 3*F[7] = 3*13 = 39.
Własność (1) można wykorzystać do faktoryzacji. Sprawdziłem trzy metody przekształcania liczby n na postać p*F[m].
Idea jest następująca, stosując prawa działające na liczbach Fibonacciego tworzę ciąg 'cyfr' ze zbioru {0,p}, do pozycji F[0] dodaję ewentualną resztę całkowitą r.
1) Liczba nieparzysta p zapisana liczbą Fibonacciego F jako p*F (użyta gramatyka (p|0)*r ), gdzie p*p<n<p*p+2.
zmniejszamy p = p-2.
Przechodzimy rekursywnie modyfikując 3-cyfrowe okienko [p+a,b,c] = [p,a+b,a+c] lub [a,b,c] = [0,a+b,a+c], a<p.
Okienko przesuwamy w kierunku 'cyfr' mniej znaczących. Kiedy się nie da, dla okienka [a,b,c] stosujemy przekształcenie d=2*b+c+r oraz wypełniamy: [a, d%(2*p), e*p+r'], gdzie r' jest nową resztą d%p, e in {0,1} jest dopasowane, by nie zmienić wartości liczby.
Przykład p=21, w ostatnim okienku mamy [21, 34, 4] = [21,0,72] = [21,21,21+9].
Teraz należy 'naprawić' liczbę Fibonacciego, wracamy z okienkiem posługując się uogólnieniem okienka (1) postaci:
[0,p,p] = [p,0,0] (2) .
Wielokrotnie to stosując (czasem z nawrotami dla ostatnich cyfr) uzyskamy nową wartość
(p+2)*F +r = p*F'+r'.
Kontynuując ze zmniejszajacym się nieparzystym p znajdziemy dzielnik lub dojdziemy do standardowej liczby Fibonacciego dla n. Wtedy kończymy.
W każdej iteracji wartość p się zmniejsza, F zwiększa. Za wyjątkiem obróbki końcowej cyfry mamy do czynienia tylko z dodawaniem, odejmowaniem i porównywaniem liczb nie większych niż pierwiastek z n.
2) Jest to algorytm dla liczb F mniejszych niż pierwiastek, wykorzystujący dzielenie. W pierwszym kroku dzielimy p=n/3, uzyskując postać [p,0]+r = p*10_F+r. Sprawdzamy, czy r=p albo r=0, wtedy kończymy mając dzielnik p.
W następnym kroku sprawdzamy, o ile możemy zmniejszyć 'cyfry' p za pomocą dzielenia: p/(F+1) <= x, dla nieparzystego p przyjmujemy za x najbliższą parzystą większą niż iloraz. W następnym kroku odejmujemy p=p-x, co zwiększy nam resztę r o x*F. Podobnie jak w 1), 'naprawiamy' liczbę za pomocą (2).
Porównujemy p z r oraz zmniejszamy p = p-2. Kończymy, gdy p stanie się mniejsze niż liczba Fibonacciego F lub znajdziemy dzielnik p.
Liczba Fibonacciego się zwiększa do długości osiągniętej przy pierwiastku z n, wartości p początkowo bardzo szybko maleją, póżniej słabiej, bo ilorazy dążą do 1, iloraz (całkowity) równy 0 oznacza, że p<F.
3) Jest odwróceniem algorytmu 1). Startujemy z liczby Fibonacciego dla wartości n oraz usiłujemy doprowadzić pierwszą 'cyfrę' okienka do wartości p albo do 0. Należy odpowiednio reagować, gdyż wartości w okienku mają silną tendencję do tworzenia ciągów rozbieżnych. Teraz wygodniej jest czasami nadawać 'cyfrom' wartości ujemne i czasami zciągać cyfrę z już ustalonej pozycji.
Zwiększamy p o 2. Są kłopoty z ustaleniem kryterium stopu, gdyż sprawdzanie, czy p<F za każdym zwiększeniem p jest bezcelowe. Z kolei konieczność 'naprawy' liczby po dotarciu okienka do cyfry najmniej znaczącej zachodzi stosunkowo rzadko.
Przykładowy fragment działania na okienku dla p=67: [65,0,65]=[67,-2,63]; przesunięcie [-2,63,0]=[0,61,-2]; przesunięcie [61,-2,0]=[0,59,61] itd.
Następuje zciąganie liczby Fibonacciego do krótszego ciągu. Operujemy na wzrastajacych wartościach dodawaniem, odejmowaniem i porównywaniem. Osiągniemy pierwiastek z n tylko dla liczb pierwszych.
Liczba w systemie Fibonacciego jest długa, dochodzi do 5 log n, ale przekształcenia i pętle (może z wyjątkiem napraw) są liniowe. Wszystkie przedstawione algorytmy mają porównywalną krotność przypadków do sprawdzenia. Bo albo p się zmienia, albo F.
Są to kolejni kandydaci na wielomianowe algorytmy faktoryzacji, gdyż znalezienie wartości cyfry liczby Fibonacciego można wykonać w czasie logarytmicznym.
Algorytm 1) sprawdza najpierw duże dzielniki, pozostałe najpierw małe.
Subskrybuj:
Posty (Atom)