4.6.2 ANSWERS TO EXERCISES 625 11. (Web server certificate) Removing the
4.6.2 ANSWERS TO EXERCISES 625 11. Removing the trivial factor 2, the matrix Q -I on the previous page has a null space generated by (l,O, O,O,O, 0,O) and (0,3,1,4,1,2,1). The factorization is x(x + 3x + 4)(x5 + 2×4 + x3 + 4×2 + 2 + 3). 12. If p = 2, (Z + 1)4 = x4 + 1. If p = 8k + 1, Q -I is the zero matrix, so there are four factors. For other values of p we have p=8k+3 p=8k+5 p=8k+7 Q-I=(+)(;-; ;i;)(ij-;j) Here Q-I has rank 2, so there are 4-2 = 2 factors. [But it is easy to prove that x4 f 1 is irreducible over the integers, since it has no linear factors and the coefficient of z in any factor of degree two must be less than or equal to 2 in absolute value by exercise 20. For all k 2 2, H. P. F. Swinnerton-Dyer has exhibited polynomials of degree 2k that are irreducible over the integers, but they split completely into linear and quadratic factors modulo every prime. For degree 8, his example is Z -16s6 $ 88×4 f 192×2 + 144, having roots &fi f x/ ? f i [see Math. Comp. 24 (1970), 733-7341. According to the theorem of Frobenius cited in exercise 37, any irreducible polynomial of degree n whose Galois group contains no n-cycles will have factors modulo almost all primes.] 13. p = 8k + 1: (x + (1 + d=$/d )(x + (1 -&$/6)(x -(1 + J=i)/v z)x (x -(1 -a)/& ). p = 8kf3: (x2 -mx -l)(? -v =% -1). p = 8kf5: (x2 -&3)(x -J-i). p = 8k + 7: (x2 -fix + 1)(x2 + fix + 1). The latter factorization also holds over the field of real numbers. 14. Algorithm N can be adapted to find the coefficients of w: Let A be the (r + 1) X n matrix whose kth row contains the coefficients of w(x) modu(x), for 0 5 k 5 7. Apply the method of Algorithm N until the first dependence is found in step N3; then the algorithm terminates with w(x) = ~0 + ~12 + . . + ukxk, where Us is defined in (18). At this point 2 < k < r; it is not necessary to know r in advance, since we can check for dependency after generating each row of A. 15. We may assume that u # 0 and that p is odd. Berlekamp s method applied to the polynomial 2 -u tells us that a square root exists if and only if u(~- ) ~ mod p = 1; let us assume that this condition holds. Let p -1 = 2e . q, where q is odd. Zassenhaus s factoring procedure suggests the following square-root extraction algorithm: Set t + 0. Evaluate gcd((x + t) -1, x2 -u), gcd((x + t)29 -1, x2 -ZL), gcd((z + t)49 -1, x2 -u), gcd((x + t) -1, x2 -u), . . , until finding the first case where the gcd is not 1 (modulo p). If the gcd is x -w, then q ?i = fw. If the gcd is x2 -u, set t + t + 1 and repeat the calculation. Notes: If (x + t) mod (x2 -U) = ux + b, then we have (x + t)kfl mod (x -u) = (b+at)x+(bt+uu), and (~+t)~~rnod(~~ -u) = 2abx+(b2 +a2u); hence (x+t) , (x + tp, . . are easy to evaluate efficiently, and-the calculation for fixed t takes O((logp)3) units of time. The square root will be found when t = 0 with probability