Dzielenia podczas faktoryzacji

Testowałem kilka rodzajów dzieleń podczas faktoryzacji liczby dziewięciocyfrowej. Nie chodziło tu o sam rozkład, bo ten już znałem, lecz o zachowywanie się dzieleń.

Stosowałem algorytm, w którym liczba n jest traktowana jako iloczyn dwu liczb
n = a*b + c
gdzie a przyjmuje kolejne wartości naturalne, b jest największe możliwe oraz c<b jest resztą.

W algorytmie dzielimy (b+a-c):(a+1) = d:(a+1) = q z resztą r, oraz podstawiamy:
b = b-q;
r = a-r;
oraz zwiększamy a = a+1;

Sprawdzałem dzielenia w których z dzielnej d tworzyłem paczki długości krotności cyfr a+1, oraz dodawałem do siebie ich kombinację liniową. Np.
784532:87  miało paczki długości 2 oraz sumy
78
78*(100-87)+45 = 78*13+45 = 1059
1059*(100-87)+32 = 1059*13+32 = 13799
Rekursją do ostatniej liczby wyznaczana jest reszta z dzielenia 13799:87, pozostałe wartosci są dodawane.
q = 78*100+1059 + (13799/87)
Dla dzielenia przez liczby ponad paczkę stosowana modyfikacja:
784532:14 ma paczki długości 2 powstające następująco:
78
-78*(14-10)+45 = -267
--267*(14-10)+32 = 1100
i dalej tak samo. Metoda jest opłacalna do wartości 1,2 wielkości paczki.

Drugim dzieleniem jest bezpośrednie przechodzenie metodą chłopów rosyjskich
(a*b+c) = (a+1)*e+f
mnożąc a przez 2, dzieląc b przez 2, zas gdy b jest nieparzyste zwiększenie c = c+a, oraz przenoszenie nadmiarów do e. Operacji jest tyle, ile wynosi logarytm binarny z b dla każdego dzielenia.

Z kroku na krok zauważyłem, że pierwsza metoda dosyć szybko się stabilizuje, zaś kolejne ilorazy cząstkowe układają się blisko ciągu arytmetycznego. Lecz to jest tylko wrażenie. Dla dalszych iteracji pojawia się szum, który modyfikuje ilorazy, zmniejszając powoli przyrost ciągu arytmetycznego. Niemniej była do dosyć dobra aproksymacja kolejnego ilorazu. Wartości na ogół były mniejsze, choć zdarzał się wzrost większy od szacowanego.

W drugiej metodzie pierwsze współczynniki reszt w kolejnych iteracjach zwiększały się o 1, dopóki potęga 2 była mniejsza niż a. Później następowało rozbieganie się wartości. Odejmowane reszty od c były potęgami 2 modulo a+1. Ta regularność zachowywała się, kiedy przeskakiwałem do kolejnej liczby pierwszej (a*b+c) = (a+m)*e+f, gdzie a oraz a+m były liczbami pierwszymi. Była jednak znacznie mniej widoczna.
Występował też szum, był on jednak związany z zapisem binarnym a aniżeli operacjami.
Ten sposób pozwala zmniejszyć krotność przypadków do krotności liczb pierwszych nie większych niż pierwiastek faktoryzowanej liczby, ze złożonością wewnętrzną logarytmiczną. Dla człowieka jednak mało strawny. Szacuję go na O( log^2 n ) przy znajomości tablicy liczb pierwszych.

Podsumowując, ten sposób faktoryzacji dosyć szybko, przy pomocy programowania dynamicznego eliminuje większość wymaganych dzieleń, zostawiając dzielenia przez bardzo małe liczby. Z kolei dla sprawdzania szacowań pojawia się mnożenie przez czynniki rzędu czwartego stopnia rozkładanej liczby.