How to Factor a Number

The security of the RSA cryptosystem is based on the difficulty of factoring integers N that are the products of two large primes p and q. If p and q are chosen well, then factoring N is indeed hard, but there are also factoring methods that work very quickly on certain kinds of integers. In order to ensure security of an RSA system, one must be careful to choose an N that does not succumb to one of the faster methods. We will discuss the Pollard rho and Pollard \(p-1\) methods first. These are not only used in general for factoring, but have been generalized to be applicable in other attacks against cryptographic systems. We then move on to CFRAC, a precursor to the state-of-the-art factoring method that is the primary topic of Chap. 12.