Algorytm Fermata
Z Wikipedii
Algorytm Fermata to jedna z metod faktoryzacji, czyli rozkładu liczby na czynniki pierwsze. Metoda ta szybko znajduje rozkład n jeśli jego dzielniki są bliskie pierwiastkowi kwadratowemu z n. Z powodu istnienia tej metody, tworząc klucze kryptograficzne oparte na iloczynach liczb pierwszych (RSA), unika się iloczynów niewiele różniących się liczb.
Działanie algorytmu polega na szukaniu pary liczb a i b takich że
- n = a2 − b2.
Tę różnicę można przedstawić jako iloczyn (a + b)(a − b); Jeśli żaden z tych czynników nie jest równy jeden, otrzymujemy faktoryzację n. Warto zauważyć że dla każdego nieparzystego n istnieje taka para liczb. Jeśli n=cd, to
- n = [(c + d) / 2]2 − [(c − d) / 2]2.
W najgorszym przypadku algorytm Fermata może działać wolniej niż naiwne szukanie dzielników n, dlatego nie ma on praktycznego zastosowania. Jego zasada działania stanowi jednak podstawę znacznie efektywniejszych algorytmów faktoryzacji, takich jak sito kwadratowe i GNFS.
[edytuj] Algorytm
Algorytm Fermata
Wejście: liczba N
Wyjście: dzielnik liczby N najbliższy pierwiastkowi
Jeśli N jest kwadratem liczby naturalnej
return sqrt(N); /*Znaleziono dzielnik*/
w przeciwnym razie
r := sqrt(N);
e := r^2 - N;
u := 2r + 1; v := 1;
Dopóki nie znaleziono dzielnika
Jeśli e=0
return (u-v)/2; /*Znaleziono dzielnik*/
w przeciwnym razie
Dopóki e<>0
Dopóki e<0
e:=e+u;
u:=u+2;
Dopóki e>0
e:=e-v;
v:=v+2;
