Kalkulator Fermatove faktorizacije

O tem kalkulatorju

Fermatova metoda faktorizacije izkorišča dejstvo, da je vsako liho celo število N mogoče zapisati kot razliko dveh kvadratov, N = a² − b² = (a−b)(a+b). Algoritem se začne pri a = ⌈√N⌉ in v vsakem koraku poveča a za 1 ter preveri, ali je a² − N sam popoln kvadrat (b²); ko je, se N takoj razcepi na (a−b)(a+b). Ta kalkulator izvede to zanko in prikaže vsak korak, ki ga je naredil pri iskanju faktorjev.

Metoda konvergira v zelo malo korakih, kadar sta si faktorja števila N blizu – njena glavna slabost je hkrati njena najpomembnejša praktična uporaba: študenti kriptografije in varnostni raziskovalci s Fermatovo faktorizacijo pokažejo, zakaj morajo biti moduli RSA zgrajeni iz praštevil, ki sta si daleč narazen, saj so moduli iz preblizu izbranih praštevil trivialno razbitni. Je tudi standardna vaja pri predmetih iz teorije števil za prikaz sklepanja z razliko kvadratov.