Algorytm Fermata

Algorytm Fermata

Algorytm Fermata jest metodą faktoryzacji, mającą na celu rozkład liczby na czynniki pierwsze. Jest szczególnie skuteczny, gdy dzielniki liczby są bliskie pierwiastkowi kwadratowemu z tej liczby. Ze względu na jego działanie, w kryptografii, zwłaszcza w systemie RSA, unika się tworzenia iloczynów liczb pierwszych, które są sobie bliskie.

Algorytm polega na poszukiwaniu pary liczb a i b, które spełniają równanie:

$n\; =\; a^2\; –\; b^2.$

Różnicę można zapisać jako iloczyn (a + b)(a – b). Jeśli żaden z tych czynników nie jest równy jeden, uzyskujemy faktoryzację n. Dla każdego nieparzystego n istnieje taka para liczb. W przypadku, gdy n = cd, faktoryzacja przybiera postać:

$n\; =\; \backslash left[\backslash frac\{c+d\}\{2\}\backslash right]^2\; –\; \backslash left[\backslash frac\{c-d\}\{2\}\backslash right]^2.$

Chociaż algorytm Fermata może być mniej efektywny niż proste wyszukiwanie dzielników, jego zasady stanowią podstawę dla bardziej zaawansowanych algorytmów faktoryzacji, takich jak sito kwadratowe oraz GNFS (general number field sieve).

Opis Algorytmu

Algorytm Fermata

Wejście: liczba N
Wyjście: dzielnik liczby N najbliższy pierwiastkowi

1. Jeśli N jest kwadratem liczby naturalnej, zwróć sqrt(N) jako dzielnik.
2. W przeciwnym razie:
   • Ustal r := ceil(sqrt(N)).
   • Oblicz e := r^2 – N.
   • Ustal u := 2r + 1 oraz v := 1.
   • Powtarzaj, aż znajdziesz dzielnik:
     • Jeśli e=0, zwróć (u-v)/2 jako dzielnik.
     • W przeciwnym razie:
       • Gdy e<0, zwiększ e o u i u o 2.
       • Gdy e>0, zmniejsz e o v i zwiększ v o 2.