Continued Fraction Factorisation Algorithm

Abstract

In mathematics, especially number theory, continued fractions allow us to represent a real number by successive divisions of integers. Applications of continued fractions include constructing rational approximations to irrational numbers and helping to solve the Diophantine and Pell’s equations. In particular, the continued fraction algorithm (CFRAC) is a powerful integer factorisation algorithm. It was described by D. H. Lehmer and R. E. Powers in 1931, whose theoretical basis will be explored today. It has been described as a general-purpose algorithm, meaning that it is suitable for factoring any integer , independent of the number’s properties. The CFRAC, in its operation, also helps us find congruences of the form . I will introduce some statements about continued fractions to motivate the purpose of this report. This will be followed with an introduction of -th complete quotients and how they produce the integers needed for the CFRAC. The CFRAC can be carried out via two methods which I will call the “A method” and “P method”, whose strengths and weaknesses will be discussed. Lastly, a faster algorithm, described by Michael A. Morrison and John Brillhart, which computerised the A method, will also be examined.