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.
Keywords for this software
References in zbMATH (referenced in 9 articles , 1 standard article )
Showing results 1 to 9 of 9.
- Bai, Shi; Brent, Richard P.; Thomé, Emmanuel: Root optimization of polynomials in the number field sieve (2015)
- Liu, Lihua; Cao, Zhengjun: On computing ord(_N(2)) and its application (2006)
- Wagstaff, S. S. jun.: Some uses of microcomputers in number theory research (1990)
- Buell, Duncan A.: Factoring: algorithms, computations, and computers (1987)
- Wunderlich, M. C.; Williams, H. C.: A parallel version of the continued fraction integer factoring algorithm (1987)
- Riesel, Hans: Modern factorization methods (1985)
- Williams, H. C.: Factoring on a computer (1984)
- Pomerance, Carl; Wagstaff, Samuel S. jun.: Implementation of the continued fraction integer factoring algorithm (1983)
- Morrison, Michael A.; Brillhart, John: A method of factoring and the factorization of (F_7) (1975)