The 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

$\begin{array}{cc}\begin{array}{cc}n=p_1{p}_2\mathrm{...}{p}_t,& p_1\le p_2\le \cdot \cdot \cdot \le p_t,\end{array}& \left(1\right)\end{array}$

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 ...