Editing Continued fraction factorization

In [[number theory]], the '''continued fraction factorization method''' ('''CFRAC''') is an [[integer factorization]] [[algorithm]]. It is a general-purpose algorithm, meaning that it is suitable for factoring any integer ''n'', not depending on special form or properties. It was described by [[Derrick Henry Lehmer|D. H. Lehmer]] and [[R. E. Powers]] in 1931,<ref>{{cite journal|last = Lehmer|first = D.H.|author2=Powers, R.E.|title = On Factoring Large Numbers|journal = Bulletin of the American Mathematical Society|volume = 37|year = 1931|issue = 10|pages = 770–776|doi = 10.1090/S0002-9904-1931-05271-X|doi-access = free}}</ref> and developed as a computer algorithm by Michael A. Morrison and [[John Brillhart]] in 1975.<ref>{{cite journal|last = Morrison|first = Michael A.|author2=Brillhart, John|title = A Method of Factoring and the Factorization of ''F''<sub>7</sub>|journal = Mathematics of Computation|url = https://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0371800-5/|volume = 29|issue = 129| pages = 183–205|date=January 1975|doi = 10.2307/2005475|jstor = 2005475|publisher = American Mathematical Society}}</ref>

The continued fraction method is based on [[Dixon's factorization method]]. It uses [[Convergent (continued fraction)|convergents]] in the [[continued fraction|regular continued fraction expansion]] of
:<math>\sqrt{kn},\qquad k\in\mathbb{Z^+}</math>.
Since this is a [[quadratic irrational]], the continued fraction must be [[periodic continued fraction|periodic]] (unless ''n'' is square, in which case the factorization is obvious).

It has a time complexity of <math>O\left(e^{\sqrt{2\log n \log\log n}}\right)=L_n\left[1/2,\sqrt{2}\right]</math>, in the [[Big O notation|O]] and [[L-notation|L]] notations.<ref>{{Cite news|last=Pomerance|first=Carl|author-link=Carl Pomerance|title=A Tale of Two Sieves|date=December 1996|periodical=Notices of the AMS|pages=1473–1485|volume=43|issue=12|url=https://www.ams.org/notices/199612/pomerance.pdf}}</ref>

==References==
{{reflist}}

==Further reading==
* {{cite book | author =Samuel S. Wagstaff, Jr. | title=The Joy of Factoring | publisher=American Mathematical Society | location=Providence, RI | year=2013 | isbn=978-1-4704-1048-3 |url=https://www.ams.org/bookpages/stml-68 |author-link=Samuel S. Wagstaff, Jr. |pages=143–171 }}

{{number theoretic algorithms}}

[[Category:Integer factorization algorithms]]


{{Numtheory-stub}}