Fermat-faktorisering beregner

Om denne beregner

Fermats faktoriseringsmetode udnytter, at ethvert ulige heltal N kan skrives som en differens mellem to kvadrater, N = a² − b² = (a−b)(a+b). Algoritmen starter ved a = ⌈√N⌉ og øger a med 1 for hvert trin, mens den kontrollerer, om a² − N selv er et perfekt kvadrat (b²); i det øjeblik det er, faktoriserer N straks til (a−b)(a+b). Denne beregner kører løkken og viser hvert trin, den tog for at finde faktorerne.

Metoden konvergerer på meget få trin, når Ns to faktorer ligger tæt på hinanden — dens største svaghed er også dens vigtigste anvendelse i den virkelige verden: studerende i kryptografi og sikkerhedsforskere bruger Fermat-faktorisering til at demonstrere, hvorfor RSA-moduli skal bygges af primtal, der ligger langt fra hinanden, da primtal valgt for tæt på hinanden gør modulet trivielt at bryde. Det er også en standardøvelse i kurser i talteori til at illustrere ræsonnement med differens af kvadrater.