Algorytm Fermata

Algorytm Fermata – metoda 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

${\displaystyle n=a^{2}-b^{2}.}$

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

${\displaystyle 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.