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.
Brak komentarzy:
Prześlij komentarz