4.5.4 FACTORING INTO PRIMES 367 would imply that (Kids web site)
4.5.4 FACTORING INTO PRIMES 367 would imply that X(X) = L(z) + O(Jl 2 o g z),* see exercise 25. Richard Brent has used a method of D. H. Lehmer to verify Riemann s hypothesis computationally for all small values of z, by showing that c(z) has exactly 75,000,OOO zeros whose imaginary part is in the range 0 < SZ < 32585736.4; all of these zeros have !J?z = 3 and c (z) # 0. [Math. Camp. 33 (1979), 1361-1372.1 In order to analyze the average behavior of Algorithm A, we would like to know how large the largest prime factor pt will tend to be. This question was first investigated by Karl Dickman [A&iv fiir Mat., As&on. och Fys. 22A, 10 (1930), l-141, who studied the probability that a random integer between 1 and z will have its largest prime factor 5 P. Dickman gave a heuristic argument to show that this probability approaches the limiting value F(a) as 2 + 00, where F can be calculated from the functional equation F(a) = 6 F(A) T, for 0 2 QI 5 1; F(a) = 1 for QI 2 1. (6) His argument was essentially this: Given 0 < t < 1, the number of integers less than x whose largest prime factor is between xt and xtfdt is xF (t) dt. The num- ber of primes p in that range is ~IT(x~+~~ T(x ) n(xt + (ln z)xt dt) - r(xt) = ) - = xt dt/t. For every such p, the number of integers n such that np 5 z and the largest prime factor of n is < p is the number of n 5 x1-t whose largest prime factor is 5 (~?- )~/(l-~), namely x1- F(t/(l -t)). Hence xF (t) dt = (x dt/t)(xl-tF(t/(l -t))), and (6) fo11ows by integration. This heuristic argu- ment can be made rigorous; V. Ramaswami [Bull. Amer. Math. Sot. 55 (1949), 1122-11271 showed that the probability in question for fixed a is asymptotically F(a)+O(l/log x), as 2 + co, and many other authors have extended the analysis [see the survey by Karl K. Norton, Memoirs Amer. Math. Sot. 106 (1971), g-271. If 3 2 cr < 1, formula (6) simplifies to F(a) = l-s, F(&)$ = 1-l: = l+lna. Thus, for example, the probability that a random positive integer 5 x has a prime factor > fi is 1 - F( 4) = In 2, about 69 percent. In all such cases, Algorithm A must work hard. The net result of this discussion is that Algorithm A will give the answer rather quickly if we want to factor a six-digit number; but for lqrge N the amount of computer time for factorization by trial division will rapidly exceed practical limits, unless we are unusually lucky. Later in this section we will see that there are fairly good ways to determine whether or not a reasonably large number n is prime, without trying all divisors up to &i. Therefore Algorithm A would often run faster if we inserted a primality test between steps A2 and A3; the running time for this improved algorithm would then be roughly proportional to pt-1, the second-largest prime factor of N, instead of to max(p,-l, ,&). By an argument analogous to