In
number theory, the continued fraction factorization method (CFRAC) is an
integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
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
D. H. Lehmer
Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s and ...
and
R. E. Powers in 1931, and developed as a computer algorithm by Michael A. Morrison and
John Brillhart in 1975.
The continued fraction method is based on
Dixon's factorization method. It uses
convergents in the
regular continued fraction expansion of
:
.
Since this is a
quadratic irrational, the continued fraction must be
periodic (unless ''n'' is square, in which case the factorization is obvious).
It has a time complexity of