Faktoryzacja według Fermata - lecz z innego wzoru

Fermat zaproponował faktoryzację z pomocą
n = a^2-b^2 = (a-b)*(a+b).

Sa też inne wzory skróconego mnożenia, np.
(a+b)^2 = a^2 + 2ab + b^2.
W szczególnym przypadku n=a*b kwadratami są:
t^2 = a^2+b^2 + 2n;
r^2 = a^2+b^2 - 2n

Możemy zacząć od a = b równym albo bliskim pierwiastkowi sqrt n, poczym zwiększać a, zmniejszać b  
a^2 + b^2 = (a+2)^2+(b-2)^2 - (4a-4b+8) = (a+2)^2+(b-2)^2 - 4(a-b+2)   (0)
sprawdzajac, czy uzyskane reszty są kwadratami. Nie musimy tego liczyć.  Wystarczy znać odległość od najbliższego kwadratu
c = t^2 - (a^2+b^2+2n) > 0                (1)
d = (a^2+b^2-2n)-r^2 > 0
oraz zmieniać 
c = c-4(a+b-2), gdy przekroczymy t^2 zmieniamy na (t+2)^2 stosując przekształcenie
(t+2)^ - t^2 = 4t+4 = 4(t+1)
które znowu pozwala przybliżać się do kwadratu po c dodatnich. Pamiętamy tylko t.
Z kwadratem r^2 robimy podobnie modyfikując dystans d od r^2, tu jest gorzej, gdyż kwadraty są stosunkowo małymi liczbami, przynajmniej początkowo.

Istotna jest parzystość. Wartości a,b są nieparzyste, zaś t, r parzyste. Wtedy uzyskamy nieparzyste dzielniki liczby n.
Przykładowo dla n=8934053 mamy inicjację
t=5978, a=b=2989
różnica c = 136 z (1), różnica d=8;
modyfikujemy a+2, b-2 uzyskując zmianę e=4(a-b+2), którą odejmujemy od c,d:
t=5978, a=2991, b=2987, c=128, d=0
mamy kwadrat dla różnicy, dla rozkładu potrzebny jest równocześnie kwadrat różnicy i kwadrat sumy. Początkowo często e>d, zatem zwiększamy r o 2.

Okazuje się, że przekształcenie (0) nie wystarczy. Potrzebne jest jeszcze jedno:
a^2+b^2 = (a+2)^2+b^2 - (4a+4)            (2)
To przekształcenie też bardzo miesza z kwadratem r.

Rozkład n następuje wtedy, gdy osiągniemy
t = 9306 = suma dzielników n,
a, b są dzielnikami n
r = 7132 = różnica dzielników n

Obliczeń jest tak dużo, że metoda ta ma wiecej przekształceń niż 'trial division'. Nie jest efektywna, choć istnieje możliwość przyspieszenia obliczeń, gdy c jest tak duże że można je częściowo zastąpić szeregiem
e + (e+16) + (e+2*16) + ... (e+k*16)
wszystko się dzieje dla stałego t, ale r początkowo trzeba liczyć niemal od początku. 

sumy iloczynów jako niedziesiątkowy system liczbowy

Zastanawiało mnie, jak zachowują się reszty, kiedy przechowuję w pamięci nie tyle wartości, co iloczyny.
Niech k będzie liczbą naturalną. Liczbę naturalną N przedstawiamy jako sumę
a_m k(k-1)...(k-m) + a_{m-1}k(k-1)...(k-m+1) + ... + a_1 k + a_0 .

Albo, myśląc o rozkładzie, co druga wartość, czyli przy a_m, 2|m będzie:
k(k-2)(k-4)...(k-m/2)
Zmiany k są jak najbardziej możliwe, zmiana k na k+2 polega na wyłączeniu z iloczynu wartości większej i zmodyfikowaniu sąsiednich wyrazów.
Okazało się, że ten sposób modyfikuje nie tylko a_i, oraz a_{i-1}, ale czasem i iloczyn mający jeden czynnik więcej.

Kiedy nauczyłem się przechodzić z k na k+2, zastanawiały mnie zmiany najmniej znaczącego składnika a_0 ze wzrostem k.
I zauważyłem, że współczynniki a_m, ... a_0 zachowują się jak cyfry, choć z zupełnie innymi zasadami przenoszenia, zaś iloczyny k...(k-i) pełnią rolę podstaw k^i.
Utworzył się w ten sposób nowy system liczbowy, chociaż nie wydaje się on pozycyjny - iloczyny trzeba zawsze zapisywać. Im większa wartość k, tym mniej składników, jak w standardowych systemach pozycyjnych niedziesiątkowych przy dużych podstawach.

A co ze współczynnikiem a_0? Jak systemach pozycyjnych przy p^k wartości tej reszty od pewnego miejsca zaczęły aproksymować przedziałami równanie logistyczne ax(b-x), tak tu takie zachowanie jest bardzo rzadkie.  Przy dużych wartościach (trzech składnikach) kolejny przyrost to prosta kombinacja liniowa, o tyle o a_0 nie możemy niemal nic powiedzieć oprócz tego, że rzadko bywa skrajna. Silne regularności występują natomiast przy współczynnikach a_2, a_1.

Przykładowo, liczbę przedstawioną jako
N = 9 * 967 * 969 + 516 * 969 + 842
przekształcamy z k=969 na k=971 następująco:
pozycja 9*967*969 chwilowo bez zmian,
różnica 971-967=4, daje zmianę 9*4 dla a_1, czyli ten wspólczynnik oblicza się następująco:
516-4*9 = 480
Dodatni, więc a_2 pozostaje bez zmian.
Ale mamy 480*969, a powinniśmy mieć 480*971, różnica 2, kontynuujemy z a_0:
842-2*480 = -118, za mało
wykorzystujemy przeniesienie 1 z a_1, czyli 480-1 = 479, a dodajemy zwiększone k=971, czyli
842-2*480+971 = 853
Nowa postać dla k=971 wygląda:
N = 9 * 969 * 971 + 479 * 971 + 853

I takie przeniesienia są bardzo częste.
Czy zatem opłaca się trzymać wartości jako sumę iloczynów? Czy lepiej używać standardowych postaci systemów pozycyjnych? Są tu dodatkowe przekształcenia pozwalające wprowadzić nowe typy cech podzielności, niewiele więcej.