Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition

4.5.4. Factoring into Primes

Several of the computational methods we have encountered in this book rest on the fact that every positive integer n can be expressed in a unique way in the form

n=p1p2...pt,p1≤p2≤⋅⋅⋅≤pt,(1)

where each p_k is prime. (When n = 1, this equation holds for t = 0.) It is unfortunately not a simple matter to find this prime factorization of n, or to determine whether or not n is prime. So far as anyone knows, it is a great deal harder to factor a large number n than to compute the greatest common divisor of two large numbers m and n; therefore we should avoid factoring large numbers whenever possible. But several ingenious ways to speed up the factoring process have been discovered, and we will now investigate some of ...