4.6.4 ANSWERS TO EXERCISES 653 (Web site developers) (~0,. . ,
4.6.4 ANSWERS TO EXERCISES 653 (~0,. . , yzn-1). The algorithms are presented in unoptimized form, for brevity and ease in exposition; the reader who implements them will notice that many things can be streamlined. Cl. [Test for simple case.] If 72 = 1, set so + ~oYo+mYl, 21 + (2o+51)(Yo+Yl)-zo, and terminate. Otherwise set m + 2+-l. C2. [Remainderize.] For 0 2 Ic < m, set (5k, xm+k) c (5k + ZnL+k, Xk -xm+k) and (Yk, ymfk) + (yk + ym+k, yk -ymfk). (Now We have X(U) mod (2~ - 1) = x0 f.. . + xm–lum-l and ~(~1)mod (urn f 1) = xm + … + ~2~~1; we will compute z(u)y(u) mod (2~~ - 1) and x(u)y(u) mod (urn + l), then we will combine the results by (57).) C3. (Recurse.] Set (20,. , ~~-1) to the cyclic convolution of (zo, . . . , xrn-i) with . , Ym-1). Also set (zm, . . . , ZZ,,-~) to the negacyclic convolution of PXT?%,…, x2,+-1) with (yn, . . . , yz,,+i). C4. [Unremainderize.] For 0 I Ic < m, set (zk, zmfk) e i(zk + zrnfk, Zk -zm+k). Now (~0,. . . , zm–l) is the desired answer. i Nl. [Test for simple case.] If n = 1, set t t xs(yo + yi), zs e t -(x0 + xl)yl, s1 + t + (xi -xs)ys, and terminate. Otherwise set m + 2Ln 2J and r + 2mi21. (The following steps use 2 +l auxiliary variables Xtj for 0 2 i < 2m and 0 < j < r, to represent 2m polynomials Xi(w) = Xi0 +Xilw+. . . +X,(,-l)~ - ; similarly, there are 2nf auxiliary variables Yij.) N2. [Initialize auxiliary polynomials.] Set Xij t X(i+,)j c xmj+i Yij + ~i+,)j + ymj+%, for 0 < i < m and 0 I j < r. (At this point we have x(u) = XO(U ) + UXl(U ) + . . . + u–l Xm-i(um), and a similar formula holds for y(u). Our strategy will be to multiply these polynomials modulo (urn7 + 1) = (u + I), by operating modulo (w f 1) on the polynomials X(W) and Y(W), finding their cyclic correlation of length 2m and thereby obtaining x(z~)y(u) = Zo(zlm) + u,&(u ) + . . + U2m–1Z2m–1(Um).) N3. [Transform.] (Now we will essentially do a fast Fourier transform on the poly- nomials (X0,. . . ,Xm–l, 0,. . . ,0) and (Yo, . . . , Y,-1, 0, . . . ,O), using w as a (2m)th root of unity. This is efficient, because multiplication by a power of w is not really a multiplication at all.) For j = [n/2] -1, . . . , 1, 0 (in this or- der), do the following for all m binary numbers s + t = (~1~12~. . . sj+lO . . .O)z + (0.. . Otj-1 . . . &~)a: Replace (Xs+t(w), X,+t+2j(w)) by the pair of polynomials (Xs+t(w) + ~(~~~)(~~~)X,+~+~j(w),X~+t(w) -w(7 )(s 2)X,+,+23(~)). (See Section 4.3.3 and Eq. 4.3.3-33. The operation Xi(w) + Xi(w) + wkXl(w) means, more precisely, that we set Xi3 +- Xij + X[(j+k) if j + k < r, otherwise Xij t Xi3 -for 0 5 j < r.) Do the same transformation on the Y s. xl(j+k-r), N4. [Recurse.] For 0 < i < 2m, set (Zie, . . . ,2,(,-l)) to the negacyclic convolution of (X0,. . . ,X+-I)) and . . . , Yz(,–I)). (Y,o, N5. [Untransform.] For j=O, 1, . . . , [n/2] (in this order), set (Zs+t(w), Zs+t+2j(w))+ ~(Zs+~(w)+ZS+t+23(w), ~–(~~~)(~~~)(Z,+t(w)–Z~+~+~~(w))), for all m choices of s and t as in step N3. N6. [Repack.] (Now we have accomplished the goal stated at the end of step N2, since it is easy to show that the transform of the Z s is the product of the transforms of the X s and the Y s) Set zi + ZZo -Z(,+i)(,-1) and Z,j+i + Ztj +Z(m+z)()-l) for 0 < j < r, for 0 5 i < m. 1