Faktoryzacja metodą (nie kolejnych) dzieleń

Liczbę złożoną nieparzystą n = p*q można przedstawić za pomocą przedstawienia liczby q = (q_m,..., q_1, q_0) w systemie binarnym następującą tablicą wartości:
n = (p*q_m, ..., p*q_1, p*q_0).
Postać ta charakteryzuje się zerami na miejscach, w których q_i=0, oraz wartościami p na miejscach, w których w zapisie binarnym q_i=1, i=0..m. Traktując poszczególne pola tablicy jako wielomian W[2], uzyskamy wartość liczby n.
Np. n = 125 możemy przedstawić jako n = (5, 5, 0, 0, 5), gdyż 125 = 5* 25, oraz 25 = 11001b. Wartość jest równa
W[2] = ((((5*2+5)*2+0)*2+0)*2+5 = 125.

Czy podana postać może służyć do znajdywania rozkładu liczby na czynniki?
W jaki sposób?
Okazuje się, że postać ta wskazuje kolejne sposoby faktoryzacji. Dysponując tabelą zapisu binarnego liczby n, za pomocą operacji niezmienniczych
n_i = 2 * n_{i-1}, i=1,...,m
można doprowadzić do postaci binarnej dzielnika.
Postępowanie zaproponowane nieco dalej sprowadza się do dzieleń przez kolejne liczby nieparzyste, lecz w nieco innej kolejności niż normalnie, z mniejszymi wartościami dzielnych. Pierwotnie próbowałem szukać, czy znajdę sposób na domyślenie się postaci binarnej dzielnika.

Pierwsze próby wyrównywania wartości w zapisie binarnym liczby n czasem skutkowały bardzo szybkim znajdywaniem dzielnika, czasem zaś wykazywały, że ten nie istnieje. Kłopot polegał na tym, że żaden algorytm nie jest w stanie przewidzieć, które pola tabeli należy wyzerować, a które zostawić ustawione, czyli przewidzieć budowę czynnika q. Należy to robić losowo, algorytmem genetycznym lub sprawdzać wszystkie możliwe przypadki.
Algorytm genetyczny ma duże szanse zapętlenia. Dodatkowo wprowadza bardzo dużo operacji wyrównujących poszczególne wartości tabeli.

Lepiej jest zastosować kombinatorykę, wtedy żegnamy się z dopasowywaniem bitów stosując wykładniczą metodę siłową.
Naszym celem jest przygotować tabelę wypełnioną równomiernie daną wartością dodatnią. Następnie zerować poszczególne pola tablicy, starając się zachować taką samą wartość na wszystkich ustawionych pozycjach.
Jeśli się to uda, dodatnia wartość w tablicy jest wartością jednego z dzielników, zaś budowa tablicy potraktowana jako liczba binarna drugim.

Praktycznie wprowadzamy komórkę reszty, do której odkładamy wszelkie nadmiary, powstały z dzielenia pierwotnego, jak i z zerowania pól tablicy.
Tabelę wypełnimy równomiernie jedną wartością b = floor(n : (2^i-1)). Dzielimy tu przez np, 3, 7, 15, 31, 63, ... w zależności od ewentualnej długości dzielnika, którego szukamy.
Pierwsze i ostatnie pole są niepuste. Przygotujemy szablon będący liczbą binarną s = (2^i-1).
Wyzerowanie bitu szablonu na pozycji k odpowiada wyzerowaniu pola tablicy, równocześnie wartość b*2^k jest dodawana do reszty. Można ją zapisać instrukcją w C++ dla maski bitowej t:
r += (s & ~t)*b.
Jeżeli teraz reszta r jest wielokrotnością szablonu (s & t), wartość reszty można bez kłopotu rozdzielić między niepuste pola tablicy, o co nam chodziło. Praktycznie sprawdzamy, czy wartość liczbowa dzieli resztę (s & t) | r. Jeśli tak, mamy do czynienia z dzielnikami (s&t) * (b+r/(s&t)) = n.

Powtarzamy dla dowolnej wariacji ustawienia pola tablicy z wyjątkiem wartości skrajnych, lub do znalezienia dzielników.


Ostatecznie dzielimy najpierw liczbę n przez s=(2^i-1) dla pewnego i, a następnie zerując odpowiednie bity szablonu dzielimy resztę przez szablon. Reszta jest liczbą nie przekraczającą połowy n, zaś liczby zadane przez schemat mają ściśle określoną długość binarną. Można też wykorzystać reszty modulo schemat.
Można się jeszcze pokusić o to, by liczby zadane szablonem nie przekroczyły pierwiastka kwadratowego z n. Zmniejszy to krotność obliczeń.

Pierwsze z dzieleń jest tak specyficzne, że można wykorzystać przyspieszone dzielenie przez odpowiedniki dziewiątki. Polega ono na pocięciu liczby na paczki długości i cyfr, na wynik składają się zapisane kolejno wartości sumy narastającej paczek.  

Przykład: 1441 = 11 * 131
Dzielimy 1441 : 3 = 480 z resztą 1, nic dalej nie można zrobić
Dzielimy 1441 : 7 = 205 z resztą 6
schemat 101b każe sprawdzić dzielenie
(2*205+6) : 101b = 416 : 5 \equiv 1 (mod 5)
Dzielimy 1441 : 15 = 96 z resztą 1
Schemat generuje 3 dzielenia przez odpowiednio 1001b, 1011b oraz 1101b.
W pierwszym przypadku mamy dzielenie
((2+4)*96+1) : 1001b = 577 : 9 \equiv 1 (mod 9),
w drugim
(4*96+1) : 1011b = 385 : 11 \equiv 0 (mod 11)
oraz dzielniki 11 oraz 96+385/11 = 96+35 = 131; w trzecim
(2*96+1) : 1101b = 193 : 13 = 11 (mod 13) .

Następuje zamiana dzieleń:
1441 : 3               1441:3
1441 : 5               416 : 5
1441 : 7               1441:7
1441 : 9               577 : 9
1441 : 11             385 : 11
                           193 : 13           

Sprawdzanie między potęgami 2, czy można przyspieszyć

Ostatni algorytm, którego nie podałem w postaci informatycznej przeszukuje 'stożek' wartości mniejszych niż liczba faktoryzowana n, którego podstawą jest 2^i, oraz 2^(2i)<n<2^(2i+1).

Zastanawiało mnie, czy muszę przeszukiwać cały ten 'stożek'. Może istnieje 'ścieżka', która doprowadzi bezpośrednio do dzielnika.
Niech n = a*b+c, gdzie a<b jest potęgą 2, oraz c<a.
Stosowana konwersja podwaja a oraz odpowiednio zmniejsza b. Wartość c zachowuje się jak chce, nie przekraczając a. Dla wartości skrajnych tworzy ciąg niemalejący.
Do dalszej iteracji wybierałem ten z przedziałów [a, a+1], [a+1, a+2] w którym spełniony był  warunek b1 < 2^k < b2, k<i.
W ten sposób dochodziłem do tego, że b po którejś iteracji stawało się potęgą 2. 

Często znajdowałem pierwiastek, ale tylko wtedy, gdy był on bliski potęgi 2. Kiedy był dalej, należało przeliczyć reszty w krotności podwojonej ostatniej znalezionej reszty. Była to często wartość bliska podstawy 'stożka'.

W szczególności dla liczb pierwszych należało sprawdzać wszystkie wartości 'stożka'. Podobny obraz dawała także liczba złożona, w której dzielniki były najdalej 'odsunięte' od potęg 2.

Zatem ten sposób nie pozwala przyspieszać, należy przerachować wszystkie wartości parzyste 'grzebienia' nie większe niż 2^(i+1). 
Dlatego 'grzebienia', gdyż sprawdzam wszystkie liczby postaci 2^k*d przedziału [2^i, 2^(i+1)), gdzie -1<k<i oraz d jest liczbą nieparzystą. Liczb takich jest tyle ile wynosi k+1, oraz 'tną' one pionowo 'stożek' na warstwy.
Zresztą, kto popatrzy na liczność przypadków przykładu poprzedniego posta, będzie wiedział, skąd nazwa 'grzebień'.