612 ANSWERS TO EXERCISES (Web file server) 45.4 19. M =
612 ANSWERS TO EXERCISES 45.4 19. M = 2O -1 is a multiple of all p for which the order of 2 modulo p divides D. To extend this idea, let al = 2 and aj+l = a: modN, where qj = p, , p, is the jth prime, and e3 = ]log lOOO/logpj]; let A = alss. Now compute b, = gcd(Aq -1, !V) for all primes q between lo3 and 105. One way to do this is to start with A mod N and then to multiply alternately by A4 mod N and A2 mod N. (A similar method was used in the 1920s by D. N. Lehmer, but he didn t publish it.) As with Algorithm B we can avoid most of the gcd s by batching; e.g., since b30r–k = gcd(A3 -Ak, N), we might try batches of 8, computing c7. = (A30 -A2g)(A30T -Az3). . . (A3 -A) mod N, then gcd(c,, N) for 33 < r 5 3334. 22. Algorithm P fails only when the random number x does not reveal the fact that n is nonprime. Say 3: is bad if zq modn = 1 or if one of the numbers z23q is = -1 (modulo n) for 0 5 j < Ic. Since 1 is bad, we have pn = (bn-l)/(n-2) < bll/(n-l), where b, is the number of bad x such that 1 5 z < n, when n is not prime. Every bad x satisfies xnY1 = 1 (modulo n). When p is prime, the number of solutions to the congruence z q G 1 (modulo p ) for 1 < z < pe is the number of solutions of qy = 0 (modulo pe- (p -1)) for 0 5 y < p - (p -l), namely gcd(q, P - (P -I)), since we may replace z by ay where a is a primitive root. Let n = nel.. . ne where the n, are distinct primes. According to the Chinese 1 remainder theorem, the number of solutions to the congruence zn- = 1 (modulo n) is nllzsr gcd(n -1, nz - (ni -l)), and this is at most nictc1.(n2 -1) since n2 is relatively prime to n -1. If some e, > 1, we have n, -1 5 $n:%, hence the number of solutions is at most $n; in this case b, 5 i$n 5 $(n -l), since n 2 9. Therefore we may assume that n is the product nl . . . n7 of distinct primes. Let n2 = 1 + 2ktq2, where ki < ... 5 k,. Then gcd(n -1, ni -1) = zkiq:, where k: = min(lc, Ici) and q: = gcd(q, qz). Modulo nz, the number of z such that xq = 1 is q:; and the number of x such that z 23q -= -1 is 23q , for 0 5 j < k:, otherwise 0. Since k 2 ki, we have b, = q: . . q: (1 + xO.,j