MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

4.6.1 ANSWERS TO EXERCISES 617 2. (a) True. (b) False if the algebraic system S contains zero divisors, nonzero numbers whose product is zero, as in exercise 1; otherwise true. (c) True when m # n, but false in general when m = n, since the leading coefficients might cancel. 3. Assume that r 5 s. For 0 5 Ic 2 r the maximum is mlmz(k f 1); for r 2 k 5 s it is mim,(r + 1); for s < k 5 r + s it is mimz(r f s + 1 -k). The least upper bound valid for all k is m,mz(r + 1). (The solver of this exercise will know how to factor the polynomial x7 + 2s6 + 3×5 + 3×4 + 3×3 + 32 + 2x + 1.) 4. If one of the polynomials has fewer than 2t nonzero coefficients, the product can be formed by putting exactly t -1 zeros between each of the coefficients, then multiplying in the binary number system, and finally using a logical AND instruction (present on most binary computers, cf. Section 4.5.4) to zero out the extra bits. For example, if t = 3, the multiplication in the text would become (1001000001)~ X (1000001001)~ = (1001001011001001001)~; if we AND this result with the constant (1001001.. lOOl)z, the desired answer is obtained. A similar technique can be used to multiply polynomials with nonnegative coefficients, when it is known that the coefficients will not be too large. 5. Polynomials of degree 5 2n can be represented as Ui(x)x + Uo(x) where deg(U1) and deg(Us) I n; and (Ul(x)x + U~(x))(V,(x)x~ f Vi(x)) = UI(X)VI(X)(X~” + 2″) -I- (Ul(x) + Uo(x))(Vl(x) + V$,(Z))X~ + Uo(x)%(x)(xn + 1). (This equation assumes that arithmetic is being done modulo 2.) Thus Eqs. 4.3.3-3, 4, 5 hold. Notes: S. A. Cook has shown that Algorithm 4.3.3C can be extended in a similar way, and exercise 4.6.4-57 describes a method requiring even fewer operations for large n. But these ideas are not useful for sparse polynomials (having mostly zero coefficients). SECTION 4.6.1 1. q(x) = 1 23×3 + 0. 22×2 -2.2x + 8 = 8~~ -4x + 8; T(X) = 28×2 + 4x + 8. 2. The manic sequence of polynomials produced during Euclid s algorithm has the coefficients (1,5,6,6,1,6,3), (1,2,5,2,2,4,5), (1,5,6,2,3,4), (1,3,4,6), 0. Hence the greatest common divisor is x3 $ 3×2 $ 4x + 6. (The greatest common divisor of a polynomial and its reverse is always symmetric, in the sense that it is a unit multiple of its own reverse.) 3. The procedure of Algorithm 4.5.2X is valid, with polynomials over S substituted for integers. When the algorithm terminates, we have U(x) = m(x), V(x) = us. Let m = deg(u), n = deg(v). It is easy to prove by induction that deg(us) + deg(vi) = n, deg(us) + deg(v2) = m, after step X3, throughout the execution of the algorithm, provided that m 2 n. Hence if m and n are greater than d = deg(gcd(u, v)) we have deg(U) < m -d, deg(V) < n -d; the exact degrees are m -dl and n -di, where di is the degree of the second-last nonzero remainder. If d = min(m, n), say d = n, we have U(z) = 0 and V(x) = 1. When U(Z) = xm -1 and w(x) = xn -1, the identity (xm -l)mod(x -1) = X mmodn -1 shows that all polynomials occurring during the calculation are manic, with integer coefficients. When u(x) = xzl -1 and u(x) = xl3 -1, we have V(x) = xl1 + x8 $ x6 f x3 + 1 and U(x) = -(x1 + xl6 $ xl4 + xl1 + zs f x6 + x3 f x). [See also Eq. 3.3.3-29, which gives an alternative formula for U(Z) and V(x).]

616 ANSWERS TO EXERCISES 4.5.4 cases where A, is respectively (1,2,3,4). Since V, lies between (@ + l)/(An f 1) and 2&?/A,, it is likely that V, 2 2@y with probability about lg(1 + y). This is not much different from a uniform distribution, so something besides the size of V, must account for the unreasonable effectiveness of Algorithm E. 37. Apply exercise 4.5.3-12 to the number fi + R, to see that the periodic part begins immediately, and run the period backwards to verify the palindromic property. [It follows that the second half of the period gives the same V s as the first, and Algorithm E could be shut down earlier by terminating it when U = U or V = V in step E5. However, the period is generally so long, we never even get close to halfway through it, so there is no point in making the algorithm more complicated.] 38. [hf. Proc. Letters 8 (1979), 28-31.1 Note that xmody = x -y [x/y] can be computed easily on such a machine, and we can get simple constants like 0 = x -Z, 1 = Lx/x], 2 = 1-t 1; we can test x > 0 by testing whether x = 1 or Lx/(x -l)] # 0. (a) First compute 1 = [lgn] in O(logn) steps, by repeatedly dividing by 2; at the same time compute k = 2 and A + 22L+1 m O(logn) steps by repeatedly setting k + 2k, A t A2. For the main computation, suppose we know that t = A , u = (A + l)m, and v = m!; then we can increase the value of m by 1 by setting m t m + 1, t t At, u t (A + l)u, v + urn; and we can double the value of m by setting m c 2m, u c u2, v c ([u/t] modA)v2, t c t2, provided that A is sufficiently large. (Consider th e number u in radix-A notation; A must be greater than ( ;n ).) Now if n = (al . ac)z, let nJ = (al . a3)2; if m = nj and k = 2j and j > 0 we can decrease j by 1 by setting k c [k/2], m c 2m+ ([n/kJ mod 2). Hence we can compute nj! for j = 1, l- 1, . . , 0 in O(logn) steps. [Another solution, due to Julia Robinson, is to compute n! = LB /(f)] when B > (2n) + ; cf. AMM 80 (1973), 250-251, 266.1 (b) First compute A = 221+2 as in (a), then find the least k 2 0 such that 2k+ !modn = 0. If gcd(n, zk!) # 1, let f(n) be this value; note that this gcd can be computed in O(logn) steps by Euclid s algorithm. Otherwise we will find the least integer m such that (lmy2,) modn = 0, and let f(n) = gcd(m, n). (Note that in this case 2k < m 5 2 k-t1, hence [m/2] 5 2k and [m/2]! is relatively prime to n; therefore ( ,my2J) mod n = 0 iff m! mod n = 0. Furthermore n # 4.) To compute m with a bounded number of registers, we can use Fibonacci numbers (cf. Algorithm 6.2.1F). Suppose we know that s = F3, s = Fj+l, t = AF3, t = AF,+ , u = (A + 1)2F3, U = (A + 1)2F3+ , v = A , w = (A + 1)2m, (2z) mod n # 0, and ( ~$ ) = 0. It is easy to reach this state of affairs with m = F3+l, for suitably large j, in O(logn) steps; furthermore A will be larger than 22(m+S). If s = 1, we set f(n) = gcd(2m + 1, n) or gcd(2m + 2, n), whichever is # 1, and terminate the algorithm. Otherwise we reduce j by 1 as follows: Set r + s, s + s -s, s + r, r + t, t + lt /tJ, t + r, r + U, 1~ + ~u / LL], U + r; then if (lwu/vt] mod A) mod n # 0, set m + m + s, w + wu, v + vt. [Can this problem be solved with fewer than O(log n) operations? Can the smallest, or the largest, prime factor of n be computed in O(logn) operations?] SECTION 4.6 1. 9×2 + 7x + 9; 5×3 + 7×2 + 2x + 6.

45.4 ANSWERS TO EXERCISES 615 31. Set r = M, qM = 4m, EM = 2m. 32. Let M = [ml, and let the places xi of each message be restricted to the range 0 < x < M3 -M2. If x > M, encode it as x3mod N as before, but if x < M change the encoding to (x + TJM)~ mod N, where y is a random number in the range M2 -M 5 y 2 M2. To decode, first take the cube root; and if the result is M3 -M2 or more, take the remainder mod M. 34. Let P be the probability that xm mod p = 1 and let Q be the probability that xm modq = 1. The probability that gcd(xm-1, N) = p or q is P(l-Q) $ &(1-P) = P f Q -2PQ. If P 5 3 or Q 5 f, this probability is > 3 max(P, Q) > i10e6, so we have a good chance of finding a factor after about 1061ogm arithmetic operations modulo N. On the other hand if P > 3 and Q > i then P zz Q z 1, since we have the general formula P = gcd(m, p -1)/p; thus m is a multiple of lcm(p -1, q -1) in this case. Let m = 2kr where r is odd, and form the sequence x1 mod N, x2 mod N, . . ..x 2k mod N; with high probability we find that the first appearance of 1 is preceded by a value y other than N -1, as in Algorithm P, hence gcd(y -1, N) = p or q. 35. Let f = (pq- -qpml) mod N. Since pmod 4 = q mod 4 = 3, we have ($) = (+) = (i) = -($) = -1, and we also have ($) = -(t) = 1. Given a message x in the range 0 5 x 2 Q(N -5), let Z = 4x + 2 or 8x f 4, whichever satisfies (3) = 1; then transmit the message Z2 mod N. To decode this message, we first use a SQRT box to find the unique number y such that y2 E Z2 mod N and (6) = 1 and y is even. Then y = 5, since the other three square roots of Z2 are N -Z and (ff%) mod N; the first of these is odd, and the other two have negative Jacobi symbols. The decoding is now completed by setting x = [y/4] if ymod4 = 2, otherwise x + [y/8]. Anybody who can decode such encodings can also find the factors of N, because the decoding of a false message Z2mod N when (5) = -1 reveals (ff)modN, a number that has a nontrivial gcd with N. 36. The mth prime equals m In m + m In In m -m + m In In m/n m -2m/ln m + O(m(log log m)2(log m)-2), by (4), although for this problem we need only the weaker estimate pm = m In m + O(m log log m). (We will assume that pm is the mth prime, since this corresponds to the assumption that V is uniformly distributed.) If we choose lnm = icdln N lnln N, where c = O(l), we find that r = c-l dm–c-2-c-2(ln In In N/n In N)- 2C2(ln $c)/ln In N + O(dm). The estimated running time (21) now simp- lifies somewhat surprisingly to the formula exp(f(c, N)dln N lnln N + O(loglog N)), where we have f(c, N) = c + (1 -(1 + In 2)/ln In N)c- The value of c that minimizes f(c, N) is J 1 -(1 + In 2)/ln In N, so we obtain the estimate exp(2Jln N In In N d/1 -(1 + In 2)/ln In N + O(log log N)). When N = 105 this gives e(N) z .33, which is still much larger than the observed behavior. Note: The partial quotients of fi seem to behave according to the distribution obtained for random real numbers in Section 4.5.3. For example, the first million partial quotients of the number 1018 + 314159 include exactly (415236, 169719, 93180, 58606)

614 ANSWERS TO EXERCISES 4.5.4 to +(z is prime) + constant + szm dt/(t -1)t In t. The constant is li 2 -In 2 = y + InIn + xn,z(ln2) /nn! = 0.35201 65995 57547 47542 73567 67736 43656 84471+. - 26. If N is not prime, it has a prime factor 4 2 fi. By hypothesis, every prime divisor p of f has an integer xp such that the order of xp modulo q is a divisor of N -1 but not of (N -1)/p. Therefore if pk divides f, the order of xp modulo q is a multiple of pk. Exercise 3.2.1.2-15 now tells us that there is an element x of order f modulo q. But this is impossible, since it implies that q2 2 (f + 1)2 2 (f + 1) r 2: N, and equality cannot hold. [Proc. Camb. Phil. Sot. 18 (1914), 29-30.1 27. If k is not divisible by 3 and if k 5 2n + 1, the number k.2 + 1 is prime iff 3 2 - k -= -1 (modulo k.2 + 1). For if this condition holds, k.2n + 1 is prime by exercise 26; and if k.2 + 1 is prime, the number 3 is a quadratic nonresidue mod k.2 + 1 by the law of quadratic reciprocity, since k.2 + 1 mod 12 = 5. [This test was stated without proof by Proth in Comptes Rendus 87 (Paris, 1878), 926.1 To implement Proth s test with the necessary efficiency, we need to be able to compute x2 mod (k.2 + 1) with about the same speed as we can compute the quantity x2 mod(2 -1). Let x 2 = A.2 + B and let A = qk + r where 0 5 r < k; we can determine q and r rapidly, when k is a single-precision number. Then x2 E B -q + r.2% (modulo k.2 + l), so the remainder is easily obtained. [To test numbers of the form 3.2 + 1 for primality, the job is only slightly more difficult; we first try random single-precision numbers until finding one that is a quadratic nonresidue mod 3.2 + 1 by the law of quadratic reciprocity, then use this number in place of 3 in the above test. If nmod4 # 0, the number 5 can be used. It turns out that 3.2n + 1 is prime when n = 1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2208, 2816, 3168, 3189, 3912; and 5.2n + 1 is prime when n = 1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947. See R. M. Robinson, Proc. Amer. Math. Sot. 9 (1958), 673-681; the additional numbers listed here were found by M. F. Plass.] 28. f(~, p2d) = 2/(~ + 1) + f(~, WP, since l/(p f 1) is the probability that A is a multiple of p. f(p, pd) = l/(p f 1) when dmodp # 0. f(2,4k + 3) = 3 since A2 -(4k + 3)B2 cannot be a multiple of 4; f(2,8k f 5) = $j since A2 -(8k + 5)B2 cannot be a multiple of 8; f(2,8k + 1) = 4 $ 4 $ i $ Q $ & + . . . = 3. f(p, d) = (2p/(p -l), 0) if d(p-1)/2 modp = (1, p -l), respectively, for odd p. 29. The number of solutions to the equation x1 $. . . + xm 5 r in nonnegative integers ziis(m$7) _> mr / r!, and each of these corresponds to a unique integer p; . . pkm 2 n. [For sharper estimates, in the special case that p, is the jth prime for all j, see N. G. de Bruijn, Indag. Math. 28 (1966), 240-247; H. Halberstam, Proc. London Math. Sot. (3) 21 (1970), 102-107.1 30. If p; . . .pz = xf (modulo qt), we can find yi such that pi . . .p$ = (j-yi) (modulo q$), hence by the Chinese remainder theorem we obtain 2d values of X such that X2 = pql. . . pz (modulo N). Such (el, . . . , e,) correspond to at most (r;2) pairs (e: ,…, el,;ey,.. , ek) having the hinted properties. Now for each of the 2d binary numbers a = (al . . . ad)2, let n, be the number of exponents (e:, . . . , eh) such that L.p l ) (qt-1)/2 f (-l) z (modulo qi); we have proved that the required number bpflintege;s X is 2 2d(C, nz)/(,;,). S mce c, na is the number of ways to choose at most r/2 objects from a set of m objects with repetitions permitted, namely ( z; 2), we have c, n , 2 ( m;t/; 2)2/2d 2 m /(2d(r/2)!). [Cf. J. Number Theory, to appear.]

4.5.4 ANSWERS TO EXERCISES 613 so we need only verify that ci,j (pi -l)(qj -1)/4 -(p -l)(q -1)/4 (modulo 2). But ci,j (pi -l)(qj -1)/4 = (ci(pi -1)/2)(Cj(9j -1)/2) is odd iff an odd number of the pi and an odd number of the q3 are = 3 (modulo 4), and this holds iff (p -l)(q -1)/4 is odd. (b) As in exercise 22, we may assume that n = ni . . . n7 where the ni = 1 + 2kaqi are distinct primes, and Ici 5 . . . 5 k,; we let gcd(n-1, ni -1) = 2k:qi and we call z bad if it falsely makes n look prime. Let II, = nlci k, and a contradiction if ki < k. If ki = Ic, there are an odd number of lci equal to k.] Notes: The probability of a bad guess is > i only if n is a Carmichael number with k, < k; for example, n = 7.13.19 = 1729, a number made famous by Ramanujan in another context. Louis Monier has extended the above analyses to obtain the following closed formulas for the number of bad 5 in general: bn= l+q ykl- 1 d; ( > n l 1 is prime if and only if it passes the x test of Algorithm P for x = x1, . . , x = xmr where m = f LlgnJ([lgnJ -1). Does there exist a sequence x1 < xs < . having this property but with m = O(log n)?] 25. This theorem was first proved rigorously by von Mangoldt [J. fiir die reine und angew. Math. 114 (1895), 255-3051, who showed in fact that the O(1) term is equal

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= ~(~l)(p.-lww =(-1)c,,,(p~-l)(q,-1)/ (Sk) (;),

4.5.4 ANSWERS TO EXERCISES 611 15. U,, = (a*–b )/a, w h ere a = i(P+&?), b = *(P-a), D = P2-4Q. Then 2n-1U,, = c, (2kyI)Pn-2k- Dk; so U, = D(p-1) 2 (modulo p) if p is an odd prime. Similarly, if V, = an + bn = Un+l -QU,-1, then ZnmlVn = c, ($)Pn-2kDk, and V, = P = P. Thus if U, = -1, we find that Upfl modp = 0. If U, E 1, we find that (QU,-I) modp = 0; here if Q is a multiple of p, U, = Pnwl (modulo p) for n > 0, so U,, is never a multiple of p; if Q is not a multiple of p, U,-l modp = 0. Therefore as in Theorem L, Ut mod N = 0 if N = p; . . . p: , gcd(N, Q) = 1, and t = lcmlsjs7(pe3-1 (p, + Ed)). Under the assumptions of this exercise, the rank of apparition of N ;s N + 1; hence N is prime to Q and t is a multiple of N + 1. Also, the assumptions of this exercise imply that each p, is odd and each Ed is fl, so t 5 2l- npT- (pJ + ip3) = 2(3) N; hence r = 1 and t = pi + ~lpE~-~. Finally, therefore, el = 1 and tl = 1. Note: If this test for primality is to be any good, we must choose P and Q in such a way that the test will probably work. Lehmer suggests taking P = 1 so that D = 1 -4Q, and choosing Q so that gcd(N, QD) = 1. (If the latter condition fails, we know already that N is not prime, unless I&D1 2 N.) Furthermore, the derivation above shows that we will want ~1 = 1, that is, D(N- )/2 = -1 (modulo N). This is another condition that determines the choice of Q. Furthermore, if D satisfies this condition, and if UN+I mod N # 0, we know that N is not prime. Example: If P = 1 and Q = -1, we have the Fibonacci sequence, with D = 5. Since 511 = -1 (modulo 23), we might attempt to prove that 23 is prime by using the Fibonacci sequence: (F, mod 23) = 0, 1, 1,2,3,5,8,13,21,11,9,20,6,3,9,12,21,10,8,18,3,21,1,22,0, . . , so 24 is the rank of apparition of 23 and the test works. However, the Fibonacci sequence cannot be used in this way to prove the primality of 13 or 17, since F7 mod 13 = 0 and Fg mod 17 = 0. When p = fl (modulo lo), we have 5(p-1)/2 modp = 1, so Fp-l (not Fp+l) is divisible by p. 17. Let f(q) = 2 lg q -1. When q = 2 or 3, the tree has at most f(q) nodes. When q > 3 is prime, let q = 1 + 41.. . qt where t 2 2 and 41, , qt are prime. The size of the tree is 5 1 + c f(qk) = 2 + f(q -1) -t < f(q). [SIAM J. Computing 7 (1975), 214-220.1 18. z(G(a) -F(a)) is th e number of 7~ 5 z whose second-largest prime factor is 5 xoL and whose largest prime factor is > !I?. Hence xG (t)dt = (T(x~+~~) -T(x )) . x1-t(G(t/(l -t)) -F(t/(l -t))) The probability that ptpl 5 fi is so1 F(t/2(1 -t))t- dt. [Curiously, it can be shown that this also equals JO1 F(t/(l -t)) dt, the average value of logptllogz, and it also equals Golomb s constant X of exercises 1.3.3-23 and 3.1-13. The derivative G (0) can be shown to equal so1 F(t/(l -t))tm2 dt = F(1) + 2F(i) + 3F(i) + = ey. The third-largest prime factor has H(a) = Joa(H(t/(l -t)) -G(t/(l -t)))t- dt and H (0) = co. See P. Billingsley, Period. Math. Hungar. 2 (1972), 283-289; J. Galambos, Acta Arith. 31 (1976), 213-218; D. E. Knuth and L. Trabb Pardo, Theoretical Camp. Sci. 3 (1976), 321-348.1

610 ANSWERS TO EXERCISES 4.5.4 11. U V A P S T output 1984 1 0 992 0 - 1981 1981 1 992 1 1981 1983 4 495 993 0 1 9932 E +22 1983 991 2 98109 1 991 1981 4 495 2 0 1 22 E +22 1984 1981 1 99099 1 1981 1984 1 1984 99101 0 1 991012 Z!! +2O The factorization 199 991 is evident from the first or last outputs. The shortness of the cycle, and the appearance of the well-known number 1984, are probably just coincidences. 12. The following algorithm makes use of an auxiliary (m + 1) X (m + 1) matrix of single-precision integers Ejk, 0 2 j, Ic 5 m; a single-precision vector (bo, br, . . . , bm); and a multiple-precision vector (20, ~1,. . , 2,) with entries in the range 0 2 xk < N. Fl. [Initialize.] Set b, + -1 for 0 5 i 2 m; then set j + 0. F2. [Next solution.] Get the next output (x, eo, el, . . , e,) produced by Algorithm E. (It is convenient to regard Algorithms E and F as coroutines.) Set k + 0. F3. [Search for odd.] If k > m go to step F5. Otherwise if ek is even, set k + k + 1 and repeat this step. F4. [Linear dependence?] If bk 2 0, then set i + bk, x + (s,z)modN, e, + e7 + E,, for 0 5 r 2 m; set k + k + 1 and return to F3. Otherwise set bk + j, x3 + x, I& + eT for 0 5 r 5 m; set j + j + 1 and return to F2. (In the latter case we have a new linearly independent solution, modulo 2, whose first odd component is ek.) F5. [Try to factor.] (Now es, ei, . , e, are even.) Set y + ((-l) p~ . . . pz ) mod N. If x = y or if 1: + y = N, return to F2. Otherwise compute gcd(a: -y, N), which is a proper factor of N, and terminate the algorithm. 1 It can be shown that this algorithm finds a factor, whenever it is possible to deduce one from the given outputs of Algorithm E. [Proof: Let the outputs of Algorithm E be (X%, EZO,. , Ei,) for 1 5 i < t, and suppose that we could find a factorization N = N1iV2 when x E Xpl.. .XFt and y E (-l)eo 2p~ 2.. . p$ (modulo N), where e, = al&, + . . . + atEi, is even for all j. Then x = +y (modulo Nr) and 2 = Ty (modulo Nz). It is not difficult to see that this solution can be transformed into a pair (x, y) that appears in step F5, by a series of steps that systematically replace (x, y) by (zz , yy ) where 2 = fy (modulo N).] 13. There are 2d values of x having the same exponents (eo, . . , e,), since we can choose the sign of 3: modulo qf arbitrarily when N = 4; . . . q$ . Exactly two of these 2d values will fail to yield a factor. 14. Since P2 = kNQ2 (modulo p) for any prime divisor p of V, we have 1 E P2(P- )/2 =_ (kNQ2)(p- )/2 s (kN)(p- )/2 (modulo p), if P $ 0.

4.5.4 ANSWERS TO EXERCISES 609 5. zmod3 = 0; smod5 = 0, 1, 4; smod7 = 0, 1, 6; zmod8 = 1, 3, 5, 7; 5 > 103. The first try is z = 105; and (105) -10541 = 484 = 222. This would also have been found by Algorithm C in a relatively short time. Thus 10541 = 83. 127. 6. Let us count the number of solutions (z, y) of the congruence N E (z -y)(z + y) (modulo p), where 0 < 2, y < p. Since N $ 0 and p is prime, z + y $ 0. For each u $ 0 there is a unique u (modulo p) such that N E UV. The congruences 5 -y E U, z + y E Y now uniquely determine x mod p and y mod p, since p is odd. Thus the stated congruence has exactly p -1 solutions (2;~). If (2, y) is a solution, so is (z, p -y) if y # 0, since (p -y) E y2; and if (5, yi) and (z, ~2) are solutions with yl # y2, we have y: E yi; hence yi = p -ys. Thus the number of different 2 values among the solutions (x, y) is (p -1)/2 if N E x2 has no solutions, or (p + 1)/2 if N EE 2 has solutions. 7. One procedure is to keep two indices for each modulus, one for the current word position and one for the current bit position; loading two words of the table and doing an indexed shift command will bring the table entries into proper alignment. (Many computers have special facilities for such bit manipulation.) 8. (We may assume that iV = 2M is even.) The following algorithm uses an auxiliary table X[l], X[2], , X[M], where X[k] represents the primality of 2k + 1. Sl. Set X[lc] t 1 for 1 5 k < M. Also set j + 1, p t 1, p t 3, q + 4. (During this algorithm p = 2j + 1, q = 2j $ 2j2; the integer variables j, k, p, q may readily be manipulated in index registers.) S2. If X[j] = 0, go to S4. Otherwise output p, which is prime, and set k + q. S3. If k 5 M, then set X[k] + 0, k + k + p, and repeat this step. S4. Setjtj+l,p+p+2,qcq+2p-2.Ifj< M,returntoS2. l A major part of this calculation could be made noticeably faster if q (instead of j) were tested against M in step S4, and if a new loop were appended that outputs 2j + 1 for all remaining X[j] that equal 1, suppressing the manipulation of p and q. Improvements in the efficiency of sieve methods for generating primes are discussed in exercise 5.2.3-15 and in Section 7.1. 9. If p2 is a divisor of n for some prime p, then p is a divisor of x(n), but not of n-1. If n = pips, where pl < p2 are primes, then ps -1 is a divisor of x(n) and therefore plp2 -1 = 0 (modulo ps -1). Since ps E 1, this means pi -1 is a multiple of p2 -1, contradicting the assumption pl < ps. [Values of n for which x(n) properly divides n -1 are called Carmichael numbers. For example, here are some small Carmichael numbers with up to six prime factors: 3.11.17, 5.13.17, 7.11.13.41, 5.7.17.19.73, 5 7.17 73 89.107.1 10. Let k, be the order of zP modulo n, and let X be the least common multiple of all the k, s. Then X is a divisor of n -1 but not of any (n -1)/p, so X = n -1. Since z;(n) modn = 1, p(n) is a multiple of k, for all p, so p(n) > X. But p(n) < n -1 when n is not prime. (Another way to carry out the proof is to construct an element z of order n -1 from the zP s, by the method of exercise 3.2.1.2-15.)

608 ANSWERS TO EXERCISES 4.5.3 42. Suppose that (IqXII = IqX -pi. We can always find integers u and v such that q = uq,-1 + vq, and p = up,-.1 + up,, where p, = Qn-~(A2,. . . ,An), since qnpn-1-qn-1pn = fl. We must have uw < 0, hence u(q,-IX -~~-1) has the same sign as v(q,X-pp,), and IqX--pi = JuI lqn-lX-p,-lI + lzll lqnX-p,l. This completes the proof, since u # 0. See Theorem 6.4s for a generalization. 43. If z is representable, so is the father of z in the Stern-Peirce tree of exercise 40; thus the representable numbers form a subtree of that binary tree. Let (U/U ) and (V/V ) be adjacent representable numbers. Then one is an ancestor of the other; say (u/u ) is an ancestor of (V/V ), since the other case is similar. Then (u/u ) is the nearest left ancestor of (V/V ), so all numbers between u/u and v/w are left descendants of (V/U ) and the mediant ((u + w)/(u + v )) is its left son. According to the relation between regular continued fractions and the binary tree, the mediant and all of its left descendants will have (U/U ) as their last representable p,/qi, while all of the mediant s right descendants will have (w/z) ) as one of the pz/qz. (The numbers p,/q, label the fathers of the turning-point nodes on the path to x.) 44. A counterexample for A4 = N = 100 is (U/U ) = 4, (U/W ) = $$. However, the identity is almost always true, because of (12); it fails only when u/u + w/v is very nearly equal to a fraction that is simpler than (U/U ). 45. See M. S. Waterman, BIT 17 (1977), 465-478. SECTION 4.5.4 1. If dk isn t prime, its prime factors are cast out before dk is tried. 2. No; the algorithm would fail if pt-1 = pt, giving 1 as a spurious prime factor. 3. Let P be the product of the first 168 primes. [Note: Although P = 19590.. .5910 is a 416-digit number, such a gcd can be computed in much less time than it would take to do 168 divisions, if we just want to test whether or not n is prime.] 4. In the notation of exercise 3.1-11, 2~ gmax(~+l~~)lp(p, X) = ; c f(l) n (1 -;); c I1>x 121 Ilk<1 where f(l) = Cl,,,, 2r gmax( –XrX)l. If 1 = 2kfe, where 0 < 6 5 1, we have f(2) = 12(3. 2- -2. 2-2e), where the function 3. 2-* -2 . 2-20 reaches a maximum of { at 0 = lg(4/3) and has a minimum of 1 at 0 = 0 and 1. Therefore the average value of 2r1gmax(Vf1,X)1 lies between 1.0 and 1.125 times the average value of p + X, and the result follows. [Algorithm B is a refinement of Pollard s original algorithm, which was based on exercise 3.1-6(b) instead of the (yet undiscovered) result in exercise 3.1-7. He showed that the least n such that X2, = X, has average value -(7r2/12)Q(m); this constant r2/12 is explained by Eq. 4.5.3-21. Hence the average value of 3n in his original method is -(~/2)~/ fi = 3.0926. Richard Brent has observed that, as m + 00, the density fl,,,,, (1 -k/m) = exp(–l(l-1)/2m+0(13/m2)) approaches a normal distribution, and we may assume that 0 is uniformly distributed. Then 3.2- -2.2-2e takes the average value 3/(41n 2), and the average number of iterations needed by Algorithm B comes to -(3/(4ln2) + a)-= 1.983& A similar analysis of the more general method in the answer to exercise 3.1-7 gives -1.9266, when p = 2.4771 is chosen optimally as the root of (p2 -1) lnp = p2 -p + 1.1