11 listopada 2016

'trial division' algorytm w jeszcze innej odsłonie

Tym razem, po długiej przerwie, kolejny algorytm 'trial division' na rozkład liczby N na czynniki. Jak moje najnowsze podejścia, znów jest prosty dla bardzo dużych wartości, zaś daje w kość dla małych dzielników.

Przedstawiam liczbę N w postaci iloczynu dwu wartości p, q i reszty r:
N = p*q + r,
gdzie p>q są liczbami nieparzystymi, r jest liczbą nieujemną, zmniejszaną by nie przekraczała podwojonego q.
Podstawowym przekształceniem jest
  (p+k)*(q-k) = pq + k(q-p) - k^2      (1) ,
albo w używanej postaci szczególnej
  (p+2)*(q-2) = pq - 2(p-q) - 4      (2) .

Inicjacja następuje dla nieparzystych p = q < sqrt(N)  lub p < sqrt N < q = p+2 gdy sqrt N jest parzyste. Liczba
  r = N - pq
jest parzysta.
W kolejnych iteracjach wykorzystujemy stary iloczyn pq by dostać nowe r następująco:
p = p+2;
q = q-2;
s = r + 2(p-q) + 4;
r = s (mod 2q);  // s można zapamiętać by mniej liczyć
p = p+ floor( s/ 2q );
jeśli r =0, dzielnikami są p i q.

niezmienniki: p, q nieparzyste, z r zabierana parzysta wielokrotność q, która jest dodawana do p.
W ten sposób p rośnie wykładniczo, zwłaszcza dla małych q, q maleje liniowo. Zmiany są bardzo małe, zwłaszcza dla q mniejszych niż pierwiastek sześcienny z 2N. Z kolei dla q mniejszych efekt wykładniczy modyfikuje p bardzo silnie.
W praktyce przeważająca krotność przypadków przypada na małe zmiany.

Do tego stopnia zmiany są małe, że dla dużych q możemy korzystać ze cech podzielności dla q i korzystając z (1) przeskakiwać nie po kolejnych nieparzystych, ale wybierać te, które nie mają dzielników 3, 5. Podobna zakusa istnieje też dla p, ale tylko dla tak dużych wartości, by p/q <2.

Przykład: fragment
sqrt 8934053  jest bliskie 2988
p = 2989, q = 2987, r = 5910
różnica 2(p-q)+4 = 8, zatem
p = 2991, q = 2985, r = 5918
jeszcze dwa razy i mamy
p = 2997, q = 2979, r = 5990 = 2*2979+32,
za duże r, dochodzi do głosu dzielenie r/ 2q , zatem uzyskujemy zwiększenie p:
p = 2999, q = 2979, r = 32

przy kolejnym zmniejszaniu q przenoszenia do p występują coraz częściej, aż od
p = 4169+2, q = 2141, r = 2*2141+3942
stają się powszechne
dochodzimy w pobliże dzielnika,
p = 8189+14 = 8203, q = 1089, r = 14*1089+986
p = 8205+14 = 8219, q = 1087, r = 14*1087
p = 8221+12 = 8233, q = 1085, r = 12*1085+1248

poczynając od wartości
p = 33971+258, q = 261, r = 258*261+284
lepiej zmienić algorytm. Tu już q jest stosunkowo bardzo małe względem p.