12 listopada 2015

Konwersje a rozkład liczb o dużych podstawach

W ostatnim poście wspominałem o sposobie 'trial division' dla liczb postaci
n = a*p+b   (1)
gdzie a,b<p oraz p^2>n.
Przy zmieniającym się a szukamy dzielników kiedy a=b (cecha podzielności, bo a*p+a = a*(p+1) = n ).
Zastanawiałem się nad przechodzeniem między różnymi p. Mamy tu aż n-sqrt(n) możliwości, przy czym dla dzielników wystarczy znajomość sqrt(n) wartości p. Albo wystarczy umieć znajdować p dla zmienianego a. Jest to obarczone błędem, jednak łatwym do skorygowania.

Niech r oznacza różnicę między p-q, gdzie
n = (a+1)*q+c = a*p+b .
Różnica ta jest bardzo duża dla małych a, zaś dla większych maleje, w szczególności dąży do 1 gdy a dąży do sqrt(n).
Kiedy konwertujemy a*p+b o k-tą wielokrotność r, wykonujemy przekształcenia:
a*p+b = a*(p-rk)+(b+ark)  (2)
Dobierając r bliskie a*r=p, możemy w ten sposób zwiększać a o prawie dowolną wartość. Oczywiście, dla większych a błąd jest mniejszy. Pozwala to pomijać podczas faktoryzacji kolejne przypadki, kiedy a nie jest dzielnikiem.

Występuje błąd, który należy skorygować. Jeśli uzyskamy wartość c>a+k, dokonujemy dzielenia c/a, co jest znacznie prostsze i szybsze niż dzielenie p/a. Uzyskaną część całkowitą odejmujemy od c uzyskując właściwą resztę.
W przypadku niedomiaru, dopasowujemy współczynnik konwersji
1+(q-c)/(a+k),
by uzyskać c z przedziału [0,a+k]. Brzegowe wartości oznaczają dzielnik. Przyrost r(a) należy modyfikować, np. odejmując iloraz nadmiaru przez przyrost k .

Zobaczmy na przykładzie.
Liczba 8934053 ma przedstawienie a*p+b = 91 * 98176 + 37,
r bliskie 98176 / 91 jest równe np. 1078.
Przejdziemy z a na 97, przyrost 6. Zatem najpierw wyznaczamy przybliżenie podstawy systemu q = p-6r = 98176 - 6*1078 = 91708.
Teraz dokonujemy właściwej konwersji, co sprowadza się do obliczenia
c = 37 + 91*1078*6 - 6*91708 = 38377
W tym miejscu mamy już a zwiększone o 6 (odejmowanie 6*q oznacza a+6),
dokonujemy korekty, w czasie której uzyskujemy nadmiar dzieleniem
38377 / 97 = 395. 
Nasza konwersja przeskoczyła o 395 za daleko. Modyfikujemy r o 395/6 oraz wracamy by c było nie większe niż a+k:
38377 - 97*395 = 62
wtedy q = 91708 + 395 = 92103.
Mamy przedstawienie liczby n = (a+6)*q+c = 97 * 92103 + 62

W ten sposób pamiętając r można przebiegać po różnych a testując kandydatów na dzielniki - liczby pierwsze a.  Po każdym przekształceniu należy jednak zmodyfikować r, tu r przechodzi na 1078 - 395/6 = 1012, co tylko przybliża p/a = 949, lecz jest wystarczające do dalszych obliczeń.

Jeśli uzyskamy wartość c>q, możemy ją zignorować. Korekta to naprawi pozostawiając właściwą wartość.