Kalkulator Fermatove faktorizacije

O ovom kalkulatoru

Fermatova metoda faktorizacije iskorištava činjenicu da se svaki neparan cijeli broj N može zapisati kao razlika dvaju kvadrata, N = a² − b² = (a−b)(a+b). Algoritam počinje s a = ⌈√N⌉ i u svakom koraku povećava a za 1, provjeravajući je li a² − N sam savršen kvadrat (b²); čim jest, N se odmah rastavlja na (a−b)(a+b). Ovaj kalkulator izvodi tu petlju i prikazuje svaki korak koji je poduzeo da pronađe faktore.

Metoda konvergira u vrlo malo koraka kada su dva faktora broja N blizu jedan drugome — njezina glavna slabost ujedno je i njezina najvažnija primjena u stvarnom svijetu: studenti kriptografije i istraživači sigurnosti koriste Fermatovu faktorizaciju kako bi pokazali zašto RSA moduli moraju biti građeni od prostih brojeva koji su međusobno daleko, jer prosti brojevi odabrani preblizu čine modul trivijalno razbijivim. Ona je i standardna vježba u kolegijima iz teorije brojeva za ilustriranje zaključivanja pomoću razlike kvadrata.