Medical web site - 4.6.3 EVALUATION OF POWERS 441 37. [HM24] (George
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-