Połączenie kilku pomysłów: sposób przedstawiania liczb za pomocą systemu Fibonacciego, liczba złożona n=d*m zawierająca tylko cyfry 0 oraz m wartości d pozwoliły na opracowanie sposobu faktoryzacji, który w pętli głównej zawiera trzy proste modyfikacje. Najbardziej kosztowne jest liczenie wartości iloczynu
k*F[2m]+r modulo p,
w którym k jest licznikiem stale dążącym do zera, r jest resztą stale rosnącą o stałą, zaś F[2m] jest stałą liczbą Fibonacciego dla danych k oraz r.
Od czasu do czasu następuje ponowne przeliczenie k oraz r, korzystając z następujących własności. W tym miejscu k jest zerem lub jedynką. Z liczby postaci
d*(F[2m]+...+F[2]+F[0]) = d*(F[2m+1]-1)
zabieramy 'cyfrę najbardziej znaczącą F[2m], dodajemy doń aktualne k oraz r oraz dzielimy z resztą przez F[2m-1]. Część całkowita zwiększona o jeden to nowe k, zaś r jest największą ujemną wartością spełniajacą wyrażenie
d*(F[2m-2]-1) + k*F[2m-1] + r = n (1)
W tym wyrażeniu modyfikujemy tylko k oraz r. Jest to niezmiennik. Dla wygody przesuwamy też indeks m cyfry Fibonacciego.
Ta część powtarza się tylko tyle razy, ile z zapisie liczby n systemem Fibonacciego jest pozycji parzystych większych od większego z dzielników. Czyli na ogól mało, poniżej log n.
W głównej części są następujące działania:
d+=2;
k-=2;
r+=2;
oraz spradzenie, czy wyrażenie k*F[]+r dzieli d. W przypadku podzielności, mamy liczbę n rozbitą na dwa składniki, oba podzielne przed d.
Zapis Fibonacciego liczby n zawiera tylko cyfry na pozycjach parzystych, zatem przy inicjacji liczba może mieć jako cyfry jedynki, dwójki i zera. Pisząc co drugą pozycję mamy np.
8934053
= 101 010010 000100 101010 100100 010101 _Fib
= 0101 010001 020000 020101 010000 010101 // tylko pozycje parzyste
= 11 101 200 211 100 111 // zapis dla faktoryzacji
Ze względu na występującą dwójkę, lepiej jest uniknąć F[2m+1]-1 -r = n postaci
9227465-1 - 293411 = n
i pzejść od razu na postać z poprzedzającą liczbą Fibonacciego przy d=3
3*3524577 + 0*3524578-1639678 =
d*(F[2m+1]-1) + k*F[2m+1]+r
Czasem są same zera i jedynki, np dla 77, wtedy dzielnik można znależć ze wspólnego dzielnika n oraz (F[2m+1]-1).
Przerzucanie wartości odbywa się coraz rzadziej, dominujące stają się obliczenia
n = d*F[]-s = 9*514228 + (9*514229 - 322060), s=5 (mod 9)
n = 11*514228 + (7*514229 - 322058)
n = 13*514228 + (5*514229 - 322056)
n = 313*10945 + (504*10946 - 8516)
n = 315*10945 + (502*10946 - 8514)
I działania są na coraz mniejszych wartościach.
Myślę o trzymaniu wartości k, F[2m] oraz r w systemie o podstawie d zamiast zwykłego dzielenia modulo. W obu przypadkach asymptotyczna złożoność to O(N log^2 n), gdzie M to mniejsza z wartości n/2 (liczba pierwsza), dzielnik n.
Okazało się, że zastosowany chwyt na cyfrze Fibonacciego działa na dowolnych liczbach. Jedyny warunek to dM<n.
Można zatem zamiast F dobrać sobie M będącą iloczynem liczb nieco większych niż d, np. pierwszych. Jako konsekwencje można przejąć kontrolę nad szukaniem dzielników przedziałami. Chcemy zmniejszać r? Niezmiennik jest postaci d(M+1)+kM+r=n. Chcemy mieć iloczyny w zakresie do 50? M=(d+2)(d+100). Można też ograniczyć sobie przedział poszukiwań dobierając odpowiednio k, M ~ n/(d+k) .
Brak komentarzy:
Prześlij komentarz