Faktorisierungsmethode von Fermat

Die Faktorisierungsmethode von Fermat ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie. Er berechnet zu einer ungeraden, zusammengesetzten Zahl zwei Teiler und , für die gilt. Die Faktorisierungsmethode von Fermat hat nur dann eine gute Laufzeit, wenn sich die zu zerlegende Zahl als Produkt annähernd gleich großer Faktoren darstellen lässt. Sie bildet zudem die Grundlage allgemeiner Faktorisierungsverfahren für große Zahlen, die in der Regel eine bessere Laufzeit aufweisen. Pierre de Fermat beschrieb diese heute nach ihm benannte Faktorisierungsmethode 1643 in einem Brief, der vermutlich an Mersenne oder Frénicle de Bessy adressiert war. In diesem Brief demonstrierte er das Verfahren, indem er die Primfaktorzerlegung von 2.027.651.281 berechnete. Einige Historiker vermuten aber, dass die Methode schon früher bekannt war.