Fermat-factorisatie calculator

Over deze rekenmachine

De factorisatiemethode van Fermat benut het feit dat elk oneven geheel getal N kan worden geschreven als een verschil van twee kwadraten, N = a² − b² = (a−b)(a+b). Het algoritme begint bij a = ⌈√N⌉ en verhoogt a bij elke stap met 1, waarbij het controleert of a² − N zelf een volkomen kwadraat (b²) is; zodra dat zo is, valt N meteen uiteen in (a−b)(a+b). Deze calculator voert die lus uit en toont elke stap die nodig was om de factoren te vinden.

De methode komt in heel weinig stappen tot een resultaat als de twee factoren van N dicht bij elkaar liggen — de belangrijkste zwakte is tegelijk het belangrijkste gebruik in de praktijk: cryptografiestudenten en beveiligingsonderzoekers gebruiken Fermat-factorisatie om te laten zien waarom RSA-moduli moeten worden opgebouwd uit priemgetallen die ver uit elkaar liggen, aangezien priemgetallen die te dicht bij elkaar zijn gekozen de modulus triviaal te kraken maken. Het is ook een standaardoefening in cursussen getaltheorie om redeneren met een verschil van kwadraten te illustreren.