Kettenbruchmethode
aus Wikipedia, der freien Enzyklopädie
| Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit ihn zu verbessern und entferne anschließend diese Markierung. |
Die Kettenbruchmethode (Abk.: CFRAC) ist ein Verfahren zur Faktorisierung (Zerlegung in Primzahlen) von natürlichen Zahlen. Da ihr Rechenaufwand sehr groß ist, lässt sie sich schwer ohne Computer durchführen. Diverse Verbesserungen im Laufe des 20. Jahrhunderts erzielen letztlich sub-exponentielle Laufzeiten und große Fortschritte bei der Zahlentheorie.
Die quadratischen Restterme der Kettenbrüche werden nach nichttrivialen Lösungen der Linearfaktoren durchsucht.
Bei diesem Verfahren muss eine Obergrenze für die in Frage kommenden Faktorbasen gewählt werden. Ist diese Grenze zu klein, gibt es kein Ergebnis, weil die tatsächlichen Primfaktoren größer sind. Ist sie zu groß, dauert die Zerlegung zu lange, weil alle möglichen Faktorbasen getestet werden müssen.
