Llogaritës i faktorizimit të Fermasë

Rreth kësaj llogaritëseje

Metoda e faktorizimit të Fermasë shfrytëzon faktin që çdo numër i plotë tek N mund të shkruhet si diferencë e dy katrorëve, N = a² − b² = (a−b)(a+b). Algoritmi fillon me a = ⌈√N⌉ dhe e rrit a me 1 në çdo hap, duke kontrolluar nëse a² − N është vetë katror i përsosur (b²); sapo të jetë, N faktorizohet menjëherë në (a−b)(a+b). Ky llogaritës e ekzekuton këtë cikël dhe tregon çdo hap që ndërmori për të gjetur faktorët.

Metoda konvergjon në shumë pak hapa kur dy faktorët e N-së janë afër njëri-tjetrit — dobësia e saj kryesore është edhe përdorimi më i rëndësishëm real: studentët e kriptografisë dhe studiuesit e sigurisë e përdorin faktorizimin e Fermasë për të demonstruar pse modulet RSA duhet të ndërtohen nga numra të thjeshtë të larguar shumë nga njëri-tjetri, pasi numrat e thjeshtë të zgjedhur shumë afër e bëjnë modulin lehtësisht të thyeshëm. Është edhe ushtrim standard në kurset e teorisë së numrave për të ilustruar arsyetimin me diferencën e katrorëve.