Kettenbruchmethode

Die Kettenbruchmethode (Abk.: CFRAC) berechnet zwei Teiler einer natürlichen Zahl, die keine Primzahl ist. Durch wiederholte Anwendung lässt sich so die Primfaktorzerlegung dieser Zahl ermitteln.

Die Kettenbruchmethode wurde 1931 von Derrick Henry Lehmer und dem Mathematik-Liebhaber Ralph Ernest Powers veröffentlicht, der auch durch zahlentheoretische Rechenergebnisse bekannt ist. Über Jahrzehnte hinweg wurde sie kaum verwendet, da sie auf den zur Verfügung stehenden Rechenmaschinen häufig nach mehreren Stunden noch keine Faktorisierung fand. Im Jahr 1970 programmierten Michael Morrison und John Brillhart die Kettenbruchmethode auf einem Großrechner und berechneten damit die Faktorisierung der siebten Fermat-Zahl. In den achtziger Jahren war die Kettenbruchmethode das Standardverfahren für die Faktorisierung großer Zahlen. Das waren damals Zahlen mit bis zu fünfzig Dezimalstellen. 1990 wurde mit dem quadratischen Sieb ein neuer Algorithmus vorgestellt, der die Nachfolge der Kettenbruchmethode antrat. Die Laufzeit der Kettenbruchmethode in O-Notation ist ${\displaystyle O\left(e^{\sqrt {2\log N\log \log N}}\right)}$, wobei N die zu faktorisierende Zahl ist.