370 ARITHMETIC 4.5.4 Algorithm B (Monte Carlo factorization). (Domain and web hosting)
370 ARITHMETIC 4.5.4 Algorithm B (Monte Carlo factorization). This algorithm outputs the prime factors of a given integer N 2 2, with high probability, although there is a chance that it will fail. Bl. [Initialize.] Set 2 c 5, x c 2, Ic +- 1, 1 +- 1, n +- N. (During this algorithm, 72 is the unfactored part of N, and the variables x and x represent the quantities x, modn and xl m~-l modn in (9), where f(z) = x2 + 1, A = 1, 1=l(m),andk=21-m. I B2. [Test primality.] If 72 is prime (see the discussion below), output n; the algorithm terminates. B3. [Factor found?] Set g t gcd(x -x, n). If g = 1, go on to step B4; otherwise output g. Now if g = n, the algorithm terminates (and it has failed, because we know that n isn t prime). Otherwise set n t n/g, x c xmodn, x t 5 mod 12, and return to step B2. (Note that g may not be prime; this should be tested. In the rare event that g isn t prime, its prime factors probably won t be determinable with this algorithm.) B4. [Advance.] Set k t k -1. If Ic = 0, set x c x, 1 c 21, Ic c 1. Set x t (x2 + 1) mod n and return to B3. fl As an example of Algorithm B, let s try to factor N = 25852 again. The third execution of step B3 will output g = 4 (which isn t prime). After six more iterations the algorithm finds the factor g = 23. Algorithm B has not distinguished itself in this example, but of course it was designed to factor big numbers. Algorithm A takes much longer to find large prime factors, but it can t be beat when it comes to removing the small ones. In practice, we should run Algorithm A awhile before switching over to Algorithm B. We can get a better idea of Algorithm B s prowess by considering the ten largest six-digit primes. The number of iterations, m(p), that Algorithm B needs to find the factor p is given in the following table: p= 999863 999883 999907 999917 999931 999953 999959 999961 999979 999983 m(P) = 276 409 2106 1561 1593 1091 474 1819 395 814 Experiments indicate that m(p) has an average value of about ZJir, and it never exceeds 12& when p < 1000000. The maximum m(p) for p < lo6 is ~~(874771) = 7685; and the maximum of m(p)/& occurs when p = 290047, m(p) .= 6251. According to these experimental results, almost all 12-digit numbers can be factored in fewer than 2000 iterations of Algorithm B (compared to roughly 100,000 divisions in Algorithm A). The time-consuming operations in each iteration of Algorithm B are the multiple-precision multiplication and division in step B4, and the gcd in step B3. If the gcd operation is slow, Pollard suggests gaining speed by accumulating the product mod rz of, say, ten consecutive (x/-x) values before taking each gcd; this replaces 90 percent of the gcd operations by a single multiplication and division while only slightly increasing the chance of failure. He also suggests starting with m = 4 instead of m = 1 in step Bl, where q is, say, & the number of iterations you are planning to use.