Kalkylator för Fermat-faktorisering

Om denna kalkylator

Fermats faktoriseringsmetod utnyttjar att varje udda heltal N kan skrivas som en skillnad mellan två kvadrater, N = a² − b² = (a−b)(a+b). Algoritmen börjar vid a = ⌈√N⌉ och ökar a med 1 i varje steg, och kontrollerar om a² − N i sig är en kvadrat (b²); i samma stund som den är det faktoriseras N direkt till (a−b)(a+b). Kalkylatorn kör den slingan och visar varje steg som togs för att hitta faktorerna.

Metoden konvergerar på mycket få steg när N:s två faktorer ligger nära varandra — dess största svaghet är också dess viktigaste användning i verkligheten: kryptografistudenter och säkerhetsforskare använder Fermat-faktorisering för att visa varför RSA-moduler måste byggas av primtal som ligger långt ifrån varandra, eftersom primtal som valts för nära varandra gör modulen trivialt knäckbar. Det är också en standarduppgift i kurser i talteori för att illustrera resonemang med skillnad mellan kvadrater.