Innumber theory, thecontinued fraction factorization method (CFRAC) is aninteger factorizationalgorithm. It is a general-purpose algorithm, meaning that it is suitable for factoring any integern, not depending on special form or properties. It was described byD. H. Lehmer andR. E. Powers in 1931,^[1] and developed as a computer algorithm by Michael A. Morrison andJohn Brillhart in 1975.^[2]

The continued fraction method is based onDixon's factorization method. It usesconvergents in theregular continued fraction expansion of

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

Since this is aquadratic irrational, the continued fraction must beperiodic (unlessn is square, in which case the factorization is obvious).

It has a time complexity of${\displaystyle O\left(e^{\sqrt{2\log n\log \log n}}\right)=L_n\left[1/2,\sqrt{2}\right]}$, in theO andL notations.^[3]

• Samuel S. Wagstaff, Jr. (2013).The Joy of Factoring. Providence, RI: American Mathematical Society. pp. 143–171.ISBN 978-1-4704-1048-3.

Thisnumber theory–related article is astub. You can help Wikipedia byadding missing information.

• v
• t
• e

• Integer factorization algorithms
• Number theory stubs

• All stub articles