CFRAC

Implementation of the continued fraction integer factoring algorithm. One of the most popular methods for factoring large integers is the continued fraction technique (CFRAC) developed by M. A. Morrison and J. Brillhart [Math. Comput. 29, 183-205 (1975; Zbl 0302.10010)]. In this very interesting paper the authors describe some major improvements to the CFRAC algorithm. Several of these, such as the large prime variation, the early abort strategy (EAS) and the choice of the multiplier, grew from suggestions originally made by Morrison and Brillhart. The addition of these refinements to CFRAC results is a very powerful factoring method. Indeed, the use of EAS alone increases the speed of factoring a 50 digit number by a factor of about 9. This paper is must reading for anyone contemplating the implementation of CFRAC.