492 ARITHMETIC 4.6.4 kth coefficient wk is the (Cpanel web hosting)
492 ARITHMETIC 4.6.4 kth coefficient wk is the bilinear form c ~i yj summed over all i and j with i + j G k (modulo n). The cyclic convolution of degree 4 can be obtained by applying rule (57). The first step is to find the factors of u4 -1, namely (U - l)(u + 1)(u2 + 1). We could write this as (u -1)(u2 + l), then apply rule (57), then use (57) again on the part modulo (u2 -1) = (U -l)(u + 1); but it is easier to generalize the Chinese remainder rule (57) directly to the case of several relatively prime factors. For example, we have z(u)y(u)modql(u)q2(u)q3(u) = al(U)q2(U)q3(U)(Z(U)Y(U)modql(u)) + a2(u)ql(u)q3( 11)(2(U)Y(U)modq2(u)) ( + u3(u)q1(11)42(u)(2(u)y(u)modg3cu,,> modql(uMuMu), (62) where ul(uMu)q3(u) + 4u)ql(u)q3(u) -t m(u)ql(u)q2(u) = 1. (The latter equation can be understood in another way, by noting that the partial fraction expansion of l/ql(u)q2(u)qdu) is ul(~)/ql(~)+u2(~)/q2(~)+~3(~)/q3(~). When each of the q s is a linear polynomial u -cy2, the generalized Chinese remainder rule reduces to ordinary interpolation as in Eq. (41), since f(u) mod (U -oi) = f(oi).) From (62) we obtain z(u)y(u) mod (u4 -1) = ( U3-tv~+U+1 Z( l)y( 1) -U3-Ui+U-1 z(-l)y(-1) -v(z(u)y(u) mod (u + 1))) mod (u4 -1). (63) The remaining problem is to evaluate z(u)y(u) mod (u2 + l), and it is time to invoke rule (58). First we reduce Z(U) and y(u) mod (u2 + l), obtaining X(U) = (TO -~2) -I-(~1 -23)~~ Y(u) = (YO -YZ) + (yl -y3)u. Then (58) tells us to evaluate X(U)Y(u) = 20 + Zru + Z2u2, and to reduce this in turn modulo (u2 + l), obtaining (20 -Z2) + 2 1~. The job of computing X(u)Y(u) is simple; we can use rule (56) with p(u) = U(U f 1) and we get 20 = XOY,, Z-1 = XOYO -(xo-x1)(Yo-Y~) + X,Y,, 2, = X,Y,. (We have thereby rediscovered the trick of Eq. 4.3.3-2 in a more systematic way.) Putting everything together yields the following realization A, B, C of degree-4 cyclic convolution: Here i stands for -1 and 2 for -2. The tensor for cyclic convolution of degree n satisfies tz,j,k = h-j,%, (65)