Faktoryzacja z użyciem systemu Fibonacciego i złożonością asymptotyczną

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

Dzielenie równoczesne przez kilka liczb - pierwsze podejście

Jeśli program najpierw przekształca, potem liczy możliwe jest dzielenie przez kilka różnych liczb równocześnie. Związane są z tym pewne kłopoty.

Mianowicie bardzo trudno o odpowiedni zapis. Następnie niezmienniki. Obmyśliłem, żeby cechę charakterystyczną był fakt, że cyfry nie mniejsze niż dana były podzielne. Następnie delikatnie przesuwam dzielnik, jak przy standardowym dzieleniu pisemnym. Nie można tego zrobić bez wsparcia lub odstępu między kolejnymi dzielnikami.

Ale powstał prototyp. Przypomina zamek błyskawiczny, działający na cyfrach liczby. Cyfry liczby stanowią jedną listę, lista kolejnych dzielników drugi. Listy łączą się ze sobą na co drugiej pozycji cyfry.

Weźmy którąś cyfrę a[i], do której doczepiony jest dzielnik d[k]. Liczba utworzona z cyfr nie mniejszych niż a[i] ma być podzielna przez d[k]. Jeśli nie jest, korzystamy z przeniesień z/do cyfry a[i-1]. Niezbędny jest tu odstęp, bo wartość pozycji i-1 zmienia się. Jest to zarazem jedna z wewnętrzych operacji dzielenia. Wartość liczby cyfr nie mniejszych niż dana jest podzielna przez d[k], co się nie zmienia, kiedy przenoszę wartości pomiędzy cyframi.

Następnie przesuwamy listę dzielników o jedną pozycję. Teraz wartość cyfry a[i] może być modyfikowana resztą uzyskaną, kiedy cyfrę a[i+1] przekształcamy w podzielną przez d[k+1]. Kiedy już się ustabilizuje, możemy kontynuować.
Kolejne przesunięcie listy dzielników, oraz cyfra a[i] ma stać się podzielna przez d[k+1].
Preferowane obliczenia zwiększają cyfry a[i] kosztem wartości a[i-1], ale pozostawiają je nieujemnymi. Zmniejszanie zbyt szybko by wrzuciło gigantyczną wartość na pozycje mniej znaczące. I tak wartości na miejscach cyfr szybko rosną, mimo ograniczeń narzucanych przez d[k].  

Dzielniki d[k] wędrują po liście od cyfr najbardziej znaczących do najmniej znaczących. Przekształcenia są lokalne, czyli mogą być wykonywane równolegle. Kiedy dzielnik d[k] dojdzie do cyfry najmniej znaczącej a[0], powinna być ona resztą z dzielenia przez d[k].

Tyle teoria. W praktyce człowiek ciągle popełnia błędy, gdyż mylą się pozycje z przypisanymi wędrującymi dzielnikami. To nie jest robota dla człowieka. Z kolei wątki ograniczone do danych cyfr traktowanych jako ulotne, powinny się sprawdzić. Na razie zaplątanie się jest mocne.

Przykład zachowania: podzielność przez [..., 7, 5, 3] liczby dziesiętnej o fragmencie [... 8 27 9 ...]
Rozpatrujemy a[i]=27, co jest podzielne przez 3.
Przesuwamy listę dzielników, sprawdzając podzielność: a[i+1]=8=10-2, a[i-1]=9=3*3. Przenosimy dwójkę uzyskując fragment [... 10 7 9 ...] o tej samej wartości, oraz spełnianych podzielnościach cyfr sąsiednich przez 5, 3 odpowiednio.
Kolejne przesunięcie dzielników, teraz a[i]=7 ma być podzielne przez 5. Zwiększenie do 10 spowoduje powstanie wartości ujemnej na pozycji a[i-1], zatem zmniejszamy do 5. Równocześnie modyfikowana jest pozycja a[i+1], by a[i+2] była podzielna przez 7. Uzyskujemy fragment [... 10x+10 5 29 ...]
I tak dalej.