Programowanie

Algorytm Fermata

Algorytm Fermata

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;

[edytuj] Zobacz też