Fortsetzung der Fraktionierungsfaktorisierung - Continued fraction factorization

In der Zahlentheorie , die Kettenbruch Faktorisierungsmethode ( CFRAC ist) eine ganze Zahl Faktorisierung Algorithmus . Es handelt sich um einen Allzweckalgorithmus, der sich zum Faktorisieren einer beliebigen Ganzzahl n eignet , unabhängig von der speziellen Form oder den Eigenschaften. Es wurde 1931 von DH Lehmer und RE Powers beschrieben und 1975 von Michael A. Morrison und John Brillhart als Computeralgorithmus entwickelt .

Die Methode der fortgesetzten Fraktion basiert auf der Faktorisierungsmethode von Dixon . Es verwendet Konvergenzien in der regulären kontinuierlichen Fraktionsexpansion von

${\ displaystyle {\ sqrt {kn}}, \ qquad k \ in \ mathbb {Z ^ {+}}}$ .

Da dies ein quadratisches Irrational ist , muss der fortgesetzte Bruch periodisch sein (es sei denn, n ist quadratisch, in diesem Fall ist die Faktorisierung offensichtlich).

Es hat eine zeitliche Komplexität von in den O- und L- Notationen. ${\ displaystyle O \ left (e ^ {\ sqrt {2 \ log n \ log \ log n}} \ right) = L_ {n} \ left [1/2, {\ sqrt {2}} \ right]}$

Verweise

Weiterführende Literatur

• Samuel S. Wagstaff, Jr. (2013). Die Freude am Factoring . Providence, RI: Amerikanische Mathematische Gesellschaft. S. 143–171. ISBN   978-1-4704-1048-3 .

Dieser Artikel im Zusammenhang mit der Zahlentheorie ist ein Stummel . Sie können Wikipedia helfen, indem Sie es erweitern .

• v
• t
• e