In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, the continued fraction factorization method (CFRAC) is an
integer factorization algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
. 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 and
R. E. Powers Ralph Ernest Powers (April 27, 1875 – January 31, 1952) was an American amateur mathematician who worked on prime numbers.
He is credited with discovering the Mersenne primes and , in 1911 and 1914 respectively. In 1934 he verified that the Mer ...
in 1931, and developed as a computer algorithm by Michael A. Morrison and
John Brillhart
John David Brillhart (November 13, 1930 – May 21, 2022) was a mathematician who worked in number theory at the University of Arizona.
Early life and education
Brillhart was born on November 13, 1930 in Berkeley, California.
He studied at the U ...
in 1975.
The continued fraction method is based on
Dixon's factorization method In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run- ...
. It uses
convergents in the
regular continued fraction expansion of
:
.
Since this is a
quadratic irrational In mathematics, a quadratic irrational number (also known as a quadratic irrational, a quadratic irrationality or quadratic surd) is an irrational number that is the solution to some quadratic equation with rational coefficients which is irreducibl ...
, the continued fraction must be
periodic (unless ''n'' is square, in which case the factorization is obvious).
It has a time complexity of