Fermat-faktorisering kalkulator

Om denne kalkulatoren

Fermats faktoriseringsmetode utnytter at ethvert oddetallig heltall N kan skrives som en differanse mellom to kvadrater, N = a² − b² = (a−b)(a+b). Algoritmen starter ved a = ⌈√N⌉ og øker a med 1 for hvert trinn, og sjekker om a² − N selv er et kvadrattall (b²); i det øyeblikket det er det, faktoriseres N umiddelbart til (a−b)(a+b). Denne kalkulatoren kjører den løkken og viser hvert trinn som ble brukt for å finne faktorene.

Metoden konvergerer på svært få trinn når de to faktorene til N ligger tett sammen — den største svakheten er også den viktigste bruken i praksis: kryptografistudenter og sikkerhetsforskere bruker Fermat-faktorisering til å vise hvorfor RSA-moduler må bygges av primtall som ligger langt fra hverandre, siden primtall som er valgt for tett gjør modulen trivielt å knekke. Det er også en standardoppgave i emner i tallteori for å illustrere resonnement med differansen mellom kvadrater.