Continued fraction factorization

The continued fraction factorization method, usually abbreviated CFRAC, is an integer factorization algorithm from number theory. It is a general-purpose method, meaning it can factor any integer n without depending on a special form or special property of the number. D. H. Lehmer and R. E. Powers described it in 1931, and Michael A. Morrison and John Brillhart developed it into a computer algorithm in 1975. The method builds on Dixon's factorization method. It uses the convergents of the regular continued fraction expansion of the square root of k times n, for positive integer k. Because that root is a quadratic irrational, the continued fraction must be periodic unless n is a perfect square, in which case the factorization is obvious. Its time complexity is O of e to the square root of 2 log n log log n, which is written L sub n of one half comma root two in L notation.