Web design - 628 ANSWERS TO EXERCISES 4.6.2 is equivalent to
628 ANSWERS TO EXERCISES 4.6.2 is equivalent to $s)v(z) + O(Z)W(Z) = f(s) (modulo T), where f(z) satisfies u(z) E W(Z)WJ(Z) + qf(s) (modulo qr). We have (4xMx) + t(xMx))~(x) + @(XV(X) -t(xb(x)h(x) = f(x) (module ~1 for all t(z). Since e(w) has an inverse modulo r, we can find a quotient t(x) by Algorithm 4.6.1D such that deg(bf–tw) < deg(w); for this t(s), deg(af+tw) 5 deg(w), since we have deg(f) 5 deg(u) = deg(w) + deg(w). Thus the desired solution is V(z) = b(x)f(x) -t(z)w(z) = b(z)f(z)modw(z), ti(z) = a(x)f(x) + t(z)w(z). If (a(z), G(x)) is another solution, we have (a(s) -G(z))w(z) G (b(z) -V(~))W(X) (modulo r). Thus if r is prime, w(x) must divide a(z) -U(s); but deg(z -E) < deg(w), so a(z) = $2) and G(x) = e(x). For p = 2, the factorization proceeds as follows (writing only the coefficients, and using bars for negative digits): Exercise 10 says that WI(X) = (11 l), WI(X) = (TiiO Oii) in one-bit two s complement notation. Euclid s extended algorithm yields a(z) = (10 0 0 0 l), b(s) = (10). The factor w(x) = x2 + clz + CO must have /cl 1 5 11 + a1 = 11, IcoJ 5 10, by exercise 20. Three applications of Hensel s lemma yield wd(z) = (13i), WJ(Z) = (1354435). Thus cl G 3 and CO = -1 (modulo 16); the only possible quadratic factor of U(X) is x2 + 32 -1. Division fails, so U(X) is irreducible. (Since we have now proved the irreducibility of this beloved polynomial by four separate methods, it is unlikely that it has any factors.) Hans Zassenhaus has observed that we can often speed up such calculations by increasing p as well as q: In the above notation, we can find A(x), B(x) such that A(z)V(z)+B(s)W(cc) = 1 ( mo d u 1o p r ), namely by taking A(x) = a(x)+pT~(s), B(z) = b(s) + p6(x), where Z(x)V(z) + 6(x)W(x) G g(x) (modulo r), a(x)V(z) + b(x)W(x) = 1 -pg(x) (modulo pr). We can also find C with C(V)C = 1 (modulo pr). In this way we can lift a squarefree factorization U(X) = w(x)w(x) (modulo p) to its unique extensions modulo p2, p4, ps, p16, etc. However, this accelerated procedure reaches a point of diminishing returns in practice, as soon as we get to double-precision moduli, since the time for multiplying multiprecision numbers in practical ranges outweighs the advantage of squaring the modulus directly. From a computational standpoint it seems best to work with the successive moduli p, p2, p4, p , . , pE, pE+ , pE+2e, pE+3e, …, where E is the smallest power of 2 with p* greater than single precision and e is the largest integer such that p has single precision. Hensel s lemma, which K. Hensel introduced in order to demonstrate the fac- torization of polynomials over the field of p-adic numbers (see exercise 4.1-31) can be generalized in several ways. First, if there are more factors, say U(X) = wi(x)wz(x)ws(x) (modulo p), we can find al(x), as(z), as(z) such that a~(x)wz(~)ws(2)+a~(z)vi(x)ws(x)+ as(x)wr(s)w2(x) = 1 (modulo p) and deg(a,) < deg(w,). (In essence, l/u(z) is expanded in partial fractions as C ai(z)/w,(z).) An exactly analogous construction now allows us to lift the factorization without changing the leading coefficients of wi and ~2; we take al(x) = al(x)f(s) mod wl(x), &(x) = az(s)f(x) mod wz(x), etc. Another important generalization is to several simultaneous moduli, of the respective forms pe, (x2 –a~)~~, . . . . (xt -f&y, when performing multivariate gcds and factorizations. Cf. D. Y. Y. Yun, Ph.D. Thesis (M.I.T., 1974). 23. The discriminant of pp(u(x)) is a nonzero integer (cf. exercise 4.6.1-12), and there are multiple factors modulo p iff p divides the discriminant. [The factorization of (22) modulo 3 is (x + 1)(x -5 -1)2(x3 +x2 -z + 1); squared factors for this polynomial occur only for p = 3, 23, 233, and 121702457. It is not difficult to prove that the