Fermat-Faktorisierungs-Rechner

Über diesen Rechner

Die Faktorisierungsmethode von Fermat nutzt die Tatsache, dass sich jede ungerade ganze Zahl N als Differenz zweier Quadrate schreiben lässt, N = a² − b² = (a−b)(a+b). Der Algorithmus beginnt bei a = ⌈√N⌉ und erhöht a in jedem Schritt um 1, wobei er prüft, ob a² − N selbst ein vollkommenes Quadrat (b²) ist; sobald dies der Fall ist, zerfällt N sofort in (a−b)(a+b). Dieser Rechner führt diese Schleife aus und zeigt jeden Schritt, den er zum Finden der Faktoren gemacht hat.

Die Methode konvergiert in sehr wenigen Schritten, wenn die beiden Faktoren von N nahe beieinander liegen – ihre größte Schwäche ist zugleich ihr wichtigster Einsatz in der Praxis: Kryptografiestudierende und Sicherheitsforscher nutzen die Fermat-Faktorisierung, um zu zeigen, warum RSA-Moduln aus weit auseinanderliegenden Primzahlen gebildet werden müssen, denn zu nah beieinander gewählte Primzahlen machen den Modulus trivial knackbar. Sie ist außerdem eine Standardübung in Zahlentheorie-Lehrveranstaltungen, um die Argumentation mit der Differenz zweier Quadrate zu veranschaulichen.