Fermat-faktorizáció kalkulátor

Erről a kalkulátorról

A Fermat-féle faktorizációs módszer azt használja ki, hogy bármely páratlan N egész szám felírható két négyzet különbségeként, N = a² − b² = (a−b)(a+b). Az algoritmus a = ⌈√N⌉ értéknél indul, és minden lépésben 1-gyel növeli a-t, ellenőrizve, hogy a² − N maga is teljes négyzet-e (b²); abban a pillanatban, ahogy az, N azonnal felbomlik (a−b)(a+b) szorzatra. A kalkulátor lefuttatja ezt a ciklust, és megmutat minden lépést, amelyet a tényezők megtalálásához megtett.

A módszer nagyon kevés lépésben konvergál, ha N két tényezője közel van egymáshoz – fő gyengesége egyben legfontosabb gyakorlati felhasználása is: a kriptográfiát tanuló diákok és a biztonsági kutatók a Fermat-faktorizációval mutatják be, miért kell az RSA-modulusokat egymástól távoli prímekből építeni, mivel a túl közel választott prímek triviálisan törhetővé teszik a modulust. Szokásos feladat a számelméleti kurzusokon is a négyzetek különbségén alapuló gondolatmenet szemléltetésére.