Web site management - 4.6.2 FACTORIZATION OF POLYNOMIALS 439 (b) Let U(Z)
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.