4.6.4 EVALUATION OF POLYNOMIALS 491 where ~(U)?(U) +
4.6.4 EVALUATION OF POLYNOMIALS 491 where ~(U)?(U) + b(u)q(u) = 1; this is essentially the Chinese remainder theorem applied to polynomials. In the third place, to evaluate the coefficients of z(~)y(~)modp(u) when p(u) has only one irreducible factor over the field of coefficients, one can use the identity duly(u) mod p(u) = (4~) mod du))(y(u) moddu)) mod p(u). (58) Repeated application of (56) (577, and (58) tends to produce efficient schemes, as we shall see. For our example problem (52), let us choose P(U) = u5 -u and apply (56); the reason for this choice of p(u) will appear as we proceed. Writing p(u) = u(u -l), rule (57) reduces to x(u)y(u) mod ~(21~ -1) = (-(U -l)zoye + u4(x(u)y(u) mod (u -1))) mod (u5 -u). (59) Here we have used the fact that z(u)y(u) mod u = zeyo; in general it is a good idea to choose p(u) in such a way that p(O) = 0, so that this simplification can be used. If we could now determine the coefficients we, wi, ws, ws of the polynomial z(u)y(u)mod(~~ -1) = wo + wiu + wsu2 + wsu3, our problem would be solved, since u4(z(u)y(u) mod (u4 -1)) mod (ti5 -u) = wou4 + wiu + w2u2 + w3u3, and the combination of (56) and (59) would reduce to (This formula can, of course, be verified directly.) The problem remaining to be solved is to compute ~(u)y(u)mod(u~ -1); and this subproblem is interesting in itself. Let us momentarily allow X(U) to be of degree 3 instead of degree 2. Then the coefficients of z(u)y(u) mod (u -1) are respectively zoyo + TlYQ + 572Y2 + 23Y1, zO!/l + ZlYO + 22Y3 + z3!/2, zoy2 + ZlYl + Z2Yo + Z3Y3, TOY3 + XlY2 + Z2Yl + Z3Y0, and the corresponding tensor is In general when deg(z) = deg(y) = n-l, the coefficients of z(u)y(u) mod (~ -1) are called the cyclic convolution of (~0, x1, . . . , qP1) and (ye, yl, . . . , ynPl). The