MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

4.6.3 EVALUATION OF POWERS 445 Fig. 13. The power tree. for all i = 1, 2, . . . , r. One way of looking at this definition is to consider a simple computer that has an accumulator and is capable of the three operations LDA, STA, and ADD; the machine begins with the number 1 in its accumulator, and it proceeds to compute the number n by adding together previous results. Note that al must equal 2, and US is either 2, 3, or 4. The shortest length, r, for which there exists an addition chain for n is denoted by l(n). Our goal in the remainder of this section is to discover as much as we can about this function l(n). The values of l(n) for small n are displayed in tree form in Fig. 14, which shows how to calculate P with the fewest possible multiplications for all n 5 100. The problem of determining l(n) was apparently first raised by H. Dellac in 1894, and a partial solution by E. de Jonquibres mentioned the factor method [cf. I IntermMiaire des MatMmaticiens 1 (1894), 20, 162-1641. In his solution, de JonquiBres listed what he felt were the values of l(p) for all prime numbers p < 200, but his table entries for p = 107, 149, 163, 179 were one too high. The factor method tells us immediately that l(mn) I l(m) + l(n), (3) since we can take the chains 1, al, . . . , a, = m and 1, bl, . . . , b, = n and form the chain 1, al, . . . , a,, arbl, . . . , u7bs = mn. We can also recast the m-ary method into addition-chain terminology. Con- sider the case m = 2k, and write n = d,,mt + dlmt- + . . . + dt in the m-ary number system; the corresponding addition chain takes the form 1,2,3, . . . ) m -2,m -1, 2d,,, 4do,. . .,mdo,mdo+dl, 2(mdo+dl), 4(mdo+dl), . . . , m(mdo+dl), m2do -t mdl + da, 7 mtdo + mt-ldl + . . . + dt. (4

444 ARITHMETIC 4.6.3 given any value of n. For example, if we want to calculate x55, we first evaluate y = x5 = x4x = (z?)~z; then we form y = yl y = (~~)~y. The whole process takes eight multiplications, while the binary method would have required nine. The factor method is better than the binary method on the average, but there are cases (n = 33 is the smallest example) where the binary method excels. The binary method can be generalized to an m-ary method as follows: Let n = domt + dlmtP1 + +. + dt, where 0 2 d, < m for 0 2 j 2 t. The computation begins by forming Z, x2, x3, . . . , Y -l. (Actually, only those powers xd3 such that dj appears in the representation of n are needed, and this observation often saves some of the work.) Then raise xdo to the mth power and multiply by xdl ; we have computed y1 = ~~~~~~~~ Next, raise y1 to the mth power and multiply by xdz, obtaining y2 = xdom2+d1m+dz. The process continues in this way until yt = xn has been computed. Whenever dj = 0, it is, of course, unnecessary to multiply by xd,. Note that this method reduces to the left-to-right binary method discussed earlier, when m = 2; there is also a less obvious right-to-left m-ary method that takes more memory but only a few more steps (see exercise 9). If m is a small prime, the m-ary method will be particularly efficient for calculating powers of one polynomial modulo another, when the coefficients are treated modulo m (see Eq. 4.6.2-5). A systematic method that gives the minimum number of multiplications for all of the relatively small values of n (in particular, for most n that occur in practical applications) is indicated in Fig. 13. To calculate xn, find n in this tree, and the path from the root to n indicates the sequence of exponents that occur in an efficient evaluation of xn. The rule for generating this power tree appears in exercise 5. Computer tests have shown that the power tree gives optimum results for all of the n listed in the figure. But for large enough values of n the power tree method is not always an optimum procedure; the smallest examples are n = 77, 154, 233. The first case for which the power tree is superior to both the binary method and the factor method is n = 23. The first case for which the factor method beats the power tree method is n = 19879 = 103.193; such cases are quite rare. (For n 5 100,000 the power tree method is better than the factor method 88,803 times; it ties 11,191 times; and it loses only 6 times.) Addition chains. The most economical way to compute xn by multiplication is a mathematical problem with an interesting history. We shall now examine it in detail, not only because it is interesting in its own right, but because it is an excellent example of the theoretical questions that arise in the study of optimum methods of computation. Although we are concerned with multiplication of powers of x, the problem can easily be reduced to addition, since the exponents are additive. This leads us to the following abstract formulation: An addition chain for n is a sequence of integers 1=&J, al, a2, . . . . a,=n (1) with the property that ai = aj + ak, for some k < j < i, (2)

4.6.3 EVALUATION OF POWERS 443 The great calculator al-Kashi stated Algorithm A about 1414 A.D. [Istorike Mat. IssledovaniG 7 (1954), 256-2571. The method is closely related to a proce- dure for multiplication that was actually used by Egyptian mathematicians as early as 1800 B.C.; for if we change step A3 to Y +-Y + 2 and step A5 to 2 +-Z + z , and if we set Y to zero instead of unity in step Al, the algorithm terminates with Y = nz. This is a practical method for multiplication by hand, since it involves only the simple operations of doubling, halving, and adding. It is often called the Russian peasant method of multiplication, since Western visitors to Russia in the nineteenth century found the method in wide use there. The number of multiplications required by Algorithm A is LlgnJ + y(n), where u(n) is the number of ones in the binary representation of n. This is one more multiplication than the left-to-right binary method mentioned at the beginning of this section would require, due to the fact that the first execution of step A3 is simply a multiplication by unity. Because of the bookkeeping time required by this algorithm, the binary method is usually not of importance for small values of n, say n 5 10, unless the time for a multiplication is comparatively large. If the value of n is known in advance, the left-to-right binary method is preferable. In some situations, such as the calculation of C? mod U(X) discussed in Section 4.6.2, it is much easier to multiply by z than to perform a general multiplication or to square a value, so binary methods for exponentiation are primarily suited for quite large n in such cases. If we wish to calculate the exact multiple-precision value of xn, when z is an integer > 1, binary methods are no help unless n is so huge that the high-speed multiplication routines of Section 4.3.3 are involved; and such applications are rare. Similarly, binary methods are usually inappropriate for raising a polynomial to a power; see R. J. Fateman, SIAM J. Computing 3 (1974), 196-213, for a discussion of the extensive literature on polynomial exponentiation. The point of these remarks is that binary methods are nice, but not a panacea. They are most applicable when the time to multiply xj . xk is essentially independent of j and Ic (e.g., for floating point multiplication, or multiplication mod m); in such cases the running time is reduced from order n to order logn. Fewer multiplications. Several authors have published statements (without proof) that the binary method actually gives the minimum possible number of multi- plications. But this is not true. The smallest counterexample is n = 15, when the binary method needs six multiplications, yet we can calculate y = x3 in Tao mul- tiplications and x l5 = y5 in three more, achieving the desired result with only five multiplications. Let us now discuss some other procedures for evaluating xn, for applications when n is known in advance (e.g., within an optimizing compiler). The factor method is based on a factorization of n. If n = pq, where p is the smallest prime factor of n and q > 1, we may calculate xn by first calculating xp and then raising this quantity to the qth power. If n is prime, we may calculate xnP1 and multiply by x. And, of course, if n = 1, we have xn with no calculation at all. Repeated application of these rules gives a procedure for evaluating xn,

442 ARITHMETIC 4.6.3 Fig. 12. Evaluation of xn, based on a right-teleft scan of the binary notation for n. tion in the hardware of a binary computer. The method can also be readily programmed for either binary or decimal computers; but it requires that the binary representation of n be scanned from left to right, while it is usually more convenient to do this from right to left. For example, with a binary computer we can shift the binary value of n to the right one bit at a time until zero is reached; with a decimal computer we can divide by 2 (or, equivalently, multiply by 5 or 4) to deduce the binary representation from right to left. Therefore the following algorithm, based on a right-to-left scan of the number, is often more convenient: Algorithm A (Right-to-left binary method for exponentiation). This algorithm evaluates 9, where n is a positive integer. (Here z belongs to any algebraic system in which an associative multiplication, with identity element 1, has been defined.) Al. [Initialize.] Set N t 72, Y t 1, 2 c Z. A2. [Halve N.] (At this point, zn = Y. ZN.) Set N + LN/2j, and at the same time determine whether N was even or odd. If N was even, skip to step A5. A3. [Multiply Y by 2.1 Set Y c 2 times Y. A4. [N = O?] If N = 0, the algorithm terminates, with Y as the answer. A5. [Square 2.1 Set 2 t Z times 2, and return to step A2. 1 As an example of Algorithm A, consider the steps in the evaluation of x23: N Y z After step Al 23 1 X After step A4 11 X X After step A4 5 x3 x2 After step A4 2 27 x4 After step A4 0 X23 Xl6 A MIX program corresponding to Algorithm A appears in exercise 2.

4.6.3 EVALUATION OF POWERS 441 37. [HM24] (George E. Collins.) Let dl, , d, be positive integers whose sum is n, and let p be prime. What is the probability that the irreducible factors of a random nth- degree integer polynomial U(Z) have degrees dl, , d,, when it is completely factored modulo p? Show that this probability is asymptotically the same as the probability that a random permutation on n elements has cycles of lengths &, . . . , d,. 38. [A4481 (V. R. Pratt.) If possible, find a way to construct proofs of irreducibility for all polynomials that are irreducible over the integers, so that the length of proof is at most a polynomial in deg(u) and the length of its coefficients. (Only a bound on the length of proof is requested here, as in exercise 4.5.4-17, not a bound on the time needed to find such a proof.) 4.6.3. Evaluation of Powers In this section we shall study the interesting problem of computing zn efficiently, given z and n, where n is a positive integer. Suppose, for example, that we need to compute x16; we could simply start with x and multiply by x fifteen times. But it is possible to obtain the same answer with only four mul- tiplications, if we repeatedly take the square of each partial result, successively forming x2, x4, x8, 216. The same idea applies, in general, to any value of n, in the following way: Write n in the binary number system (suppressing zeros at the left). Then replace each 1 by the pair of letters SX, replace each 0 by S, and cross off the SX that now appears at the left. The result is a rule for computing xn, if S is interpreted as the operation of squaring, and if x is interpreted as the operation of multiplying by x. For example, if n = 23, its binary representation is 10111; so we form the sequence SX S SX SX SX and remove the leading SX to obtain the rule SSXSXSX. This rule states that we should square, square, multiply by z, square, multiply by x, square, and multiply by x ; in other words, we should successively compute x2, x4, x5, x1 , x1 , x22, x23. This binary method is easily justified by a consideration of the sequence of exponents in the calculation: If we reinterpret S as the operation of multiplying by 2 and x as the operation of adding 1, and if we start with 1 instead of x, the rule will lead to a computation of n because of the properties of t,he binary number system. The method is quite ancient; it appeared before 200 B.C. in Pingala s Hindu classic Chandah-sOtra [see B. Datta and A. N. Singh, History of Hindu Mathematics 1 (Bombay: 1935), 761; however, there seem to be no other references to this method outside of India during the next 1000 years. A clear discussion of how to compute 2n efficiently for arbitrary n was given by al-Uqlidisi of Damascus in 952 A.D.; see The Arithmetic of al-Zlqlidisi by A. S. Saidan (Dordrecht: D. Reidel, 1975), 341-342, where the general ideas are illustrated for n = 51. See also al-BirQni s Chronology of Ancient Nations, ed. and translated by E. Sachau (London: 1879), 132-136; this eleventh-century Arabic work had great influence. The S-and-X binary method for obtaining xn requires no temporary storage except for x and the current partial result, so it is well suited for incorpora-

440 ARITHMETIC 4.6.2 31. [HMW] Let p be an odd prime and let d 2 1. Show that there exists a number n(p, d) having the following two properties: (a) For all integers t, exactly n(p, d) irreducible polynomials q(z) of degree d, modulo p, satisfy (x+t)(pd-1)/2 modq(z) = 1. (b) For all integers 0 2 tl < tz < p, exactly n(p,d) irreducible polynomials q(z) of degree d, modulo p, satisfy (Z + tl)(pd- )/2 mod q(z) = (z + t2)(pd-1)/2 modq(z). b 32. [A4301 (Cyclotomic polynomials.) Let Qn(s) = &I,I,,,,,,,,,,=,(~ -uk), where w = elriln; thus, the roots of QJ~(z) are the complex nth roots of unity that aren t mth roots for m < n. (a) Prove that a(z) is a polynomial with integer coeffi- cients, and that Xn -1 = j–J *d(x); *n(x) = U(xd -lynld). dn dn (Cf. exercises 4.5.2-10(b) and 4.5.3-28(c).) (b) P rove that Q%(x) is irreducible over the integers, hence the above formula is the complete factorization of xn -1 over the integers. [Hint: If f(x) is an irreducible factor of Iln(x) over the integers, and if c is a complex number with f(s) = 0, prove that f(sP) = 0 for all primes p not dividing n. It may help to use the fact that x -1 is squarefree modulo p for all such primes.] (c) Discuss the calculation of Iln(x), and tabulate the values for n < 15. 33. [A4181 True or false: If U(X) # 0 and the complete factorization of U(X) modulo p is PI(X) . . . p?(~)~r, then u(x)/gcd(zl(x), U (X)) = PI(X). . .p7(x). b 34. [A&?.51 (Squarefree factorization.) It is clear that any primitive polynomial of a unique factorization domain can be expressed in the form U(X) = u,(x)u~(x)~u~(x) . . . , where the polynomials Us are squarefree and relatively prime to each other. This representation, in which Us is the product of all the irreducible polynomials that divide U(X) exactly j times, is unique except for unit multiples; and it is a useful way to represent polynomials that participate in multiplication, division, and gcd operations. Let GcD(~(x),v(x)) b e a p rocedure that returns three answers: GCD(u(x), 4×1) = (d(x), 4x)/d(x), v(x)/d(x)), where d(x) = gcd(u(x), V(X)). The modular method described in the text following Eq. (25) always ends with a trial division of u(x)/d(x) and v(x)/d(x), t o make sure that no unlucky prime has been used, so the quantities u(x)/d(x) and w(x)/d( x) are byproducts of the gcd computation; thus we can compute GCD(u(x), V(X)) essentially as fast as gcd(u(x), V(X)) when we are using a modular method. Devise a procedure that obtains the squarefree representation (ul(x), 112(x), . . . ) of a given primitive polynomial u(x) over the integers. Your algorithm should perform exactly e computations of a GCD, where e is the largest subscript with LL~(x) # 1; furthermore, each GCD calculation should satisfy (27), so that Hensel s construction can be used. 35. [A&Z?] (D. Y. Y. Yun.) Design an algorithm that computes the squarefree rep- resentation (WI(X), WZ(X), . . .) of W(X) = gcd(zl(x), V(X)) over the integers, given the squarefree representations (Us, Us, . . . ) and (VI(X), 2)2(x), . . . ) of U(X) and V(X). 36. [MZ?7] Extend the procedure of exercise 34 so that it will obtain the squarefree representation (ul(x), UZ(X), . . . ) of a given polynomial U(X) when the coefficient arith- metic is performed modulo p.

4.6.2 FACTORIZATION OF POLYNOMIALS 439 (b) Let U(Z) = v(z)w(z), where deg(v) = m and deg(w) = k. Use the results proved in exercise 20 to show that we always have ]zl]]w] 5 f(m, k) [ul, where f(m, k) = ($)(ik). (c) Let u(Q,. . . ,zt) = ZI(ZI,. ,z~)w(zI,. . . ,~t), where w and w have the respective degrees m3 and Ic, in x3. Prove that lwllwl 2 (f(ml, h). f(mt, kt)) %4. b 22. [M.Z4] (Hensel s Lemma.) Let u(x), Qx), we(x), a(x), b(x) be polynomials with integer coefficients, satisfying the relations U(X) = w,(x)w,(x) (modulo p ), a(x)v,(x) + b(x)?&(x) G 1 (modulo p), where p is prime, e 2 1, we(x) is manic, deg(a) < deg(w,), deg(b) < deg(w,), and deg(u) = deg(w,) + deg(w,). Show how to compute polynomials v,+~(z) = we(z) and w,+r(x) = w,(x) (modulo p ), satisfying the same conditions with e increased by 1. Furthermore, prove that w,+r(x) and we+l(x) are unique, modulo pew . Use your method for p = 2 to prove that (22) is irreducible over the integers, starting with its factorization mod 2 found in exercise 10. (Note that Euclid s extended algorithm, exercise 4.6.1-3, will get the process started for e = 1.) 23. [HM93] Let u(z) be a squarefree polynomial with integer coefficients. Prove that there are only finitely many primes p such that u(x) is not squarefree modulo p. 24. [A&%] The text speaks only of factorization over the integers, not over the field of rational numbers. Explain how to find the complete factorization of a polynomial with rational coefficients, over the field of rational numbers. 25. [M.%] What is the complete factorization of x5 + x4 + x2 + x + 2 over the field of rational numbers? 26. [ZOO] Let dl, . , d, be the degrees of the irreducible factors of U(X) modulo p, with proper multiplicity, so that dl+. . . + d, = n = deg(u). Explain how to compute the set { deg(w) I u(x) c W(Z)W(Z) (modulo p) f or some W(Z), W(Z)} by performing O(r) operations on binary bit strings of length n. 27. [HM30] Prove that a random primitive polynomial over the integers is almost always irreducible, in some appropriate sense. 28. [A&%] The distinct-degree factorization procedure is lucky when there is at most one irreducible polynomial of each degree d; then gd(x) never needs to be broken into factors. What is the probability of such a lucky circumstance, when factoring a random polynomial of degree n, modulo p, for fixed n as p + oo? 29. [A&% ] Let g(s) be a product of two or more distinct irreducible polynomials of degree d, modulo an odd prime p. Prove that gcd(g(x), t(~)(~~-l)/~ -1) will be a proper factor of g(x) with probability 2 l/2 -1/(2pd), f or any fixed g(z), when t(z) is selected at random from among the p2d polynomials of degree < 2d modulo p. 30. [M%] Prove that if q(z) is an irreducible polynomial of degree d, modulo p, and if t(x) is any polynomial, then the value of (t(~)+t(z)~ +t(~)~ +. . . +t(~)~~-l) mod q(z) is an integer (i.e., a polynomial of degree 5 0). Use this fact to design a probabilistic algorithm for factoring a product gd(x) of degree-d irreducibles, analogous to (21), for the case p = 2.

438 ARITHMETIC 4.6.2 16. [M.W] (a) Given that f(x) is an irreducible polynomial modulo a prime p, of degree n, prove that the pn polynomials of degree less than n form a field under arithmetic modulo f(x) and p. (Note: The existence of irreducible polynomials of each degree is proved in exercise 4; therefore fields with p elements exist for all primes p and all n 2: 1.) (b) Show that any field with p elements has a primitive root element < such that the elements of the field are (0, 1, [, t2,. . . , Epne2}. [Hint: Exercise 3.2.1.2-16 provides a proof in the special case n = 1.1 (c) If f( z ) is an irreducible polynomial modulo p, of degree n, prove that xpm -x is divisible by f(x) if and only if m is a multiple of n. (It follows that we can test irreducibility rather quickly: A given nth degree polynomial f(x) is irreducible modulo p if and only if xpn -x is divisible by f(x) and gcd(xP -2, f(z)) = 1 for all primes o dividing n.) 17. [MB] Let F be a field with 132 elements. How many elements of F have order f, for each integer f with 1 5 f < 132? (The order of an element a is the least positive integer m such that urn = 1.) F 18. [M%] Let U(X) = ~~5~ + . . . + ~0, ZL~ # 0, be a primitive polynomial with integer coefficients, and let V(Z) be the manic polynomial defined by V(X) = IL, - . u(x/u,) = xn + I&-1x-l + un-2unxn-2 +. . .uou, - . (a) Given that w(x) has the complete factorization PI(X). pr(x) over the integers, where each pj(x) is manic, what is the complete factorization of U(X) over the integers? (b) If W(X) = xm + W,-#—l + . . . + Wc iS a faCtOr Of 21(X), prove that wk iS a IUUkipk ofu,”-lpk for0 <- k

4.6.2 FACTORIZATION OF POLYNOMIALS 437 3. [M.%] Let us, . . . . u7(z) be polynomials over a field S, with 2~j(z) relatively prime to uk(z) for all j # k. For any given polynomials WI(X), . . . , wI(z) over S, prove that there is a unique polynomial V(X) over S such that d&v) < deg(ul) + . . + deg(u,) and V(Z) = I+(Z) (modulo uj(z)) for 1 2 j 5 r. (Compare with Theorem 4.3.2C.) 4. [HA4%?] Let anp be the number of manic irreducible polynomials of degree n, modulo a prime p. Find a formula for the generating function G,,(z) = c, unpzn. [Hint: Prove the following identity connecting power series: f(z) = cj2] g(zj)/j if and only if g(z) = xn>l p(n)f(z )/n .] What is lim,,, a,,/p ? - 5. [HMXI] Let A,, be the average number of factors of a randomly selected poly- nomial of degree n, modulo a prime p. Show that lim,,,A,, = H,. What is the limiting average value of 27, when there are r factors? 6. [M~I] (J. L. Lagrange, 1771.) Prove the congruence (9). [Hint: Factor x1, - z in the field of p elements.] 7. [AL% ] Prove Eq. (14). 8. [HiWW] How can we be sure that the vectors output by Algorithm N are linearly independent? 9. [20] Explain how to construct a table of reciprocals mod 101 in a simple way, given that 2 is a primitive root of 101. b 10. [.zI] Find the complete factorization of the polynomial U(X) in (22), modulo 2, using Berlekamp s procedure. 11. [,% ,!?IFind the complete factorization of the polynomial u(x) in (22), modulo 5. b 12. [IV@,% ] Use Berlekamp s algorithm to determine the number of factors of u(z) = x4 + 1, modulo p, for all primes p. [Hint: Consider the cases p = 2, p = 8k + 1, p=8k+3,p=8k+5,p=8k+7s eparately; what is the matrix Q? You need not discover the factors; just determine how many there are.] 13. [M,%] Give an explicit formula for the factors of x4 + 1, modulo p, for all odd primes p, in terms of the quantities m, fi, m (if such square roots exist modulo p). 14. [A4,%] (H. Zassenhaus.) Let W(X) be a solution to (8), and let W(X) = n(z -s) where the product is over all 0 2 s < p such that gcd(u(z), V(X) -s) # 1. Explain how to compute w(z), given U(Z) and v(z). [Hint: Eq. (14) implies that ,w(z) is the polynomial of least degree such that u(z) divides zu(v(z)).] b 15. [A& 71 Design an algorithm to calculate the square root of a given integer u modulo a given prime p, i.e., to find an integer v such that v2 = u (modulo p) whenever such a w exists. Your algorithm should be efficient even for very large primes p. (Note that a solution to this problem leads to a procedure for solving any given quadratic equation modulo p, using the quadratic formula in the usual way.)

436 ARITHMETIC 4.6.2 method to determine 4~) modulo pe for sufficiently large e. Hensel s construction appears to be computationally superior to the Chinese remainder approach; but it is valid directly only when gcd(d(s), u(z)/d(z)) = 1 or w@(x), 4+W) = 1, (27) since the idea is to apply the techniques of exercise 22 to one of the factorizations @)u(z) = ij(z)ul(z) or @)u(x) G $z)vl(z) (modulo p). Exercises 34 and 35 show that it is possible to arrange things so that (27) holds whenever necessary. The gcd algorithms sketched here are significantly faster than those of Section 4.6.1 except when the polynomial remainder sequence is very short. Perhaps the best general procedure would be to start with the computation of gcd(u(s), V(X)) modulo a fairly small prime p, not a divisor of both e(v) and e(v). If the result q(x) is 1, we re done; if it has high degree, we use Algorithm 4.6.lC; otherwise we use one of the above methods, first computing a bound for the coefficients of a(~) based on the coefficients of U(X) and W(Z), and on the (small) degree of q(z). As in the factorization problem, we should apply this procedure to the reverses of u(z), V(X) and reverse the result, if the trailing coefficients are simpler than the leading ones. Multivariate polynomials. Similar techniques lead to useful algorithms for fac- torization or gcd calculations on multivariate polynomials with integer coeffi- cients. It is convenient to deal with the polynomial u(z1, . . . , Q) by working modulo the irreducible polynomials 22 -a~, . . . , it —at, which play the r61e of p in the above discussion. Since W(X) mod (x-a) = w(a), the value of u(zl, . . . , xt) is the univariate polynomial u(x~, ~2,. . . , at). When the integers u2, . . . , at have been chosen so that u(zl, as, . . . , at) has the same degree in ~1 as ~(21, ~2,. . . , Q), an appropriate generalization of Hensel s construction will lift squarefree fac- torizations of this univariate polynomial to factorizations modulo (~2 -u2)Q, . ..) (xt -utp, where nj is the degree of x3 in u; at the same time we can also work modulo an appropriate integer prime p. As many as possible of the uj should be zero, so that sparseness of the intermediate results is retained. For details, see P. S. Wang, Math. Comp. 32 (1978), 1215-1231, in addition to the papers by Musser and by Moses and Yun cited earlier. EXERCISES b 1. [M24] Let p be prime. What is the probability that a random polynomial of degree n has a linear factor (a factor of degrea l), when n 2 p? Show that this probability is more than 4. (Assume that each of the pn manic polynomials modulo p is equally likely.) What is the average number of linear factors? b 2. [A& 5] (a) Show that any manic polynomial U(Z), over a unique factorization domain, may be expressed uniquely in the form u(5) = ?J(x)2w(x), where W(Z) is squarefree (has no factor of positive degree of the form d(z) ) and both W(Z) and W(X) are manic. (b) (E. R. Berlekamp.) How many manic polynomials of degree n are squarefree modulo p, when p is prime?