4.5.4 FACTORING INTO PRIMES 389 [Cf. G. H. (Web design online)
4.5.4 FACTORING INTO PRIMES 389 [Cf. G. H. Hardy and E. M. Wright 0), 522.11; see als The size of prime factors has a remarkable connection with permutations: The average number of bits in the lath largest prime factor of a random n-bit integer is asymptotically the same as the average length of the lath largest cycle of a random n-element permutation, as n + 00. [See D. E. Knuth and L. Trabb Pardo, Theoretica Comp. Sci. 3 (1976), 321-348.1 It follows that Algorithm A usually finds a few small factors and then begins a long-drawn-out search for the big ones that are left. Factoring a la Monte Carlo. Near the beginning of Chapter 3, we observed that a random number generator chosen at random isn t very random. This principle, which worked against us in that chapter, has the redeeming virtue that it leads to a surprisingly efficient method of factorization, discovered by J. M. Pollard [BIT 15 (1975), 331-3341. Th e number of computational steps in Pollard s method is on the order of &, so it is significantly faster than Algorithm A when N is large. According to (7) and Fig. 11, the running time will usually be well under N1i4. Let f(z) be any polynomial with integer coefficients, and consider the two sequences defined by x0 = yyo = A; xm+l = f(x,) mod N, ym+l = f(yd modn (9) where p is any prime factor of N. It follows that yrn = xm mod P, for m 2 1. UOi Now exercise 3.1-7 shows that we will have ym = y~(~)-i for some m 2 1, where l(m) is the greatest power of 2 that is 2 m. Thus xm -x~(~).-i will be a multiple of p. Furthermore if f(y)modp behaves as a random mapping from the set {O,l,. . . , p - 1) into itself, exercise 3.1-12 shows that the average value of the least such m will be of order Jir. In fact, exercise 4 below shows that this average value for random mappings is less than 1.625 Q(p), where the function Q(p) x m was defined in Section 1.2.11.3. If the different prime divisors of N correspond to different values of m (as they almost surely will, when N is large), we will be able to find them by calculating gcd(x, -~l(~)-i, N) for m = 1, 2, 3, . . .X until the unfactored residue is prime. From the theory in Chapter 3, we know that a linear polynomial f(z) = ax + c will not be sufficiently random for our purposes. The next-simplest case is quadratic, say f(x) = x2 + 1; although we don t know that this function is sufficiently random, our lack of knowledge tends to support the hypothesis of randomness, and empirical tests show that this f does work essentially as predicted. In fact, f is probably slightly better than random, since x2 + 1 takes on only i(p + 1) distinct values mod p. Therefore the following procedure is reasonable: