算法导论 30 Problems 答案

30-1

a

本题和题目 4.2-5 类似。

$\begin{array}{rl}(ax+b)(cx+d)& =ac{x}^2+(bc+ad)x+bd\\ & =ac{x}^2+((a+b)(c+d)-ac-bd)x+bd\end{array}$

计算三次乘法 $u=(a+b)(c+d),v=ac,w=bd$，那么可以计算出多项式的结果为 $v{x}^2+(u-v-w)x+w$。

b

此处假设 $n$ 是一个偶数。不失一般性，假设现在有两个多项式 ${\displaystyle A(x)=\sum _{i=0}^{n-1}{a}_i{x}^i,B(x)=\sum _{i=0}^{n-1}{b}_i{x}^i}$，现在计算多项式 $C(x)=A(x)\cdot B(x)$ 的系数。假设多项式 $A(x),B(x)$ 的次数 $n$ 都为偶数。

首先考虑第一种分治策略，即分成高阶系数一半和低阶系数一半。

令 ${\displaystyle A_1(x)=\sum _{i=0}^{n/2-1}{a}_i{x}^i,A_2=\sum _{i=0}^{n/2-1}{a}_{i+n/2}{x}^i}$。那么有 $A(x)=A_2(x)x^{n/2}+A_1(x)$。类似的，令 ${\displaystyle B_1(x)=\sum _{i=0}^{n/2-1}{b}_i{x}^i,B_2=\sum _{i=0}^{n/2-1}{b}_{i+n/2}{x}^i}$。那么有 $B(x)=B_2(x)x^{n/2}+B_1(x)$。那么考虑计算如下 $3$ 个多项式的乘积（均是 $n/2$ 次的多项式）：

$\begin{array}{rl}u(x)& =(A_1(x)+A_2(x))\cdot (B_1(x)+B_2(x))\\ v(x)& =A_2(x)\cdot B_2(x)\\ w(x)& =A_1(x)\cdot B_1(x)\end{array}$

那么最终可以得到 $C(x)=v(x)\cdot x^n+(u(x)-v(x)-w(x))\cdot x^{n/2}+w(x)$。可以验证：

$\begin{array}{rl}C(x)& =u(x)\cdot x^n+(u(x)-v(x)-w(x))\cdot x^{n/2}+w(x)\\ & =A_2(x)\cdot B_2(x)\cdot x^n+A_1(x)\cdot B_2(x)\cdot x^{n/2}+A_2(x)\cdot x^{n/2}\cdot B_1(x)+A_1(x)\cdot B_1(x)\\ & =(A_2(x)x^{n/2}+A_1(x))\cdot (B_2(x)x^{n/2}+B_1(x))\\ & =A(x)\cdot B(x)\end{array}$

令 $T(n)$ 表示这种分治策略的运行时间。首先花费 $3T(n/2)$ 的时间计算出多项式 $u(x),v(x),w(x)$，再花费 $\mathrm{\Theta }(n)$ 的时间将这三个多项式合成计算结果 $C(x)=A(x)\cdot B(x)$，因此可以写出关于 $T(n)$ 的递推式：

$$T(n)=3T(n/2)+\mathrm{\Theta }(n)$$

根据主定理的第 1 个条件，可以得到 $T(n)=\mathrm{\Theta }(n^{\lg 3})$。

接下来考虑第二种分治策略，即按照系数下标的奇偶性划分。

令 ${\displaystyle A_1(x)=\sum _{i=0}^{n/2-1}{a}_{2i}{x}^i,A_2=\sum _{i=0}^{n/2-1}{a}_{2i+1}{x}^i}$。那么有 $A(x)=A_2(x^2)x+A_1(x^2)$。类似的，令 ${\displaystyle B_1(x)=\sum _{i=0}^{n/2-1}{b}_{2i}{x}^i,B_2=\sum _{i=0}^{n/2-1}{b}_{2i+1}{x}^i}$。那么有 $B(x)=B_2(x^2)x+B_1(x^2)$。那么考虑计算如下 $3$ 个多项式的乘积（均是 $n/2$ 次的多项式）：

$\begin{array}{rl}u(x)& =(A_1(x)+A_2(x))\cdot (B_1(x)+B_2(x))\\ v(x)& =A_2(x)\cdot B_2(x)\\ w(x)& =A_1(x)\cdot B_1(x)\end{array}$

那么最终可以得到 $C(x)=v(x^2)\cdot x^2+(u(x^2)-v(x^2)-w(x^2))\cdot x+w(x^2)$。可以验证：

$\begin{array}{rl}C(x)& =v(x^2)\cdot x^2+(u(x^2)-v(x^2)-w(x^2))\cdot x+w(x^2)\\ & =A_2(x^2)\cdot B_2(x^2)\cdot x^2+A_1(x^2)\cdot B_2(x^2)\cdot x+A_2(x^2)\cdot x\cdot B_1(x)+A_1(x^2)\cdot B_1(x^2)\\ & =(A_2(x^2)x+A_1(x^2))\cdot (B_2(x^2)x+B_1(x^2))\\ & =A(x)\cdot B(x)\end{array}$

可见，子问题的数量和规模和第一种分治策略一致，并且可以 $\mathrm{\Theta }(n)$ 的时间根据分治结果合并出 $C(x)$，因此这种分治策略所需要的时间开销为 $\mathrm{\Theta }(n^{\lg 3})$。

c

先将 $n$ 位二进制数 $a,b$ 在 $O(n)$ 的时间内转化成度数为 $n$ 的多项式 ${\displaystyle A(x)=\sum _{i=0}^{n-1}{a}_i{x}^i,B(x)=\sum _{i=0}^{n-1}{b}_i{x}^i}$。其中 $a_k$ 表示 $a$ 的第 $k$ 比特（$b_k$ 同理）。

使用上面的分治算法计算出多项式 $C(x)=A(x)\cdot B(x)$，需要花费 $O(n^{\lg 3})$，然后花费 $O(n)$ 的时间处理数组 $C$ 的进位，并转化成二进制数 $c$，最终只需要 $O(n^{\lg 3})$ 的时间就可以计算出 $c$。以下过程是计算出 $c$ 的过程 MULTIPLY-FFT。$O(n^{\lg 3})$ 中的每个步骤均摊下来，只花费 $O(1)$（即常数）的比特操作。

MULTIPLY-FFT(a, b, n)
  convert binary numbers a, b into polynomials A, B of degree n
  m = 2 ^ (⌈lg n⌉ + 1)
  for i = 1 to m - n
    INSERT(A, 0)
    INSERT(B, 0)
  C = FFT-INV(FFT(A, m) ⋅ FFT(B, m), m)
  cap = 0
  for i = 0 to m - 1
    cap = cap + C[i]
    C[i] = cap % 2
    cap = ⌊cap / 2⌋
  convert polynomial C to binary number c
  return c

30-2

a

考虑将 ${\omega }_{n_2}^{j_2{k}_2},{\omega }_{n_3}^{j_3{k}_3},\dots ,{\omega }_{n_d}^{j_d{k}_d}$ 都视为是常数。那么有

$\begin{array}{rl}{y}_{k_1,k_2,\dots ,k_d}& =\sum _{j_1=0}^{n_1-1}\sum _{j_2=0}^{n_2-1}\dots \sum _{j_d=0}^{n_d-1}{a}_{k_1,k_2,\dots ,k_d}{\omega }_{n_1}^{j_1{k}_1}{\omega }_{n_2}^{j_2{k}_2}\dots {\omega }_{n_d}^{j_d{k}_d}\\ & =\sum _{j_2=0}^{n_2-1}\sum _{j_3=0}^{n_3-1}\dots \sum _{j_d=0}^{n_d-1}\sum _{j_1=0}^{n_1-1}{a}_{k_1,k_2,\dots ,k_d}{\omega }_{n_1}^{j_1{k}_1}{\omega }_{n_2}^{j_2{k}_2}\dots {\omega }_{n_d}^{j_d{k}_d}\\ & =\sum _{j_2=0}^{n_2-1}\sum _{j_3=0}^{n_3-1}\dots \sum _{j_d=0}^{n_d-1}\sum _{j_1=0}^{n_1-1}{a}_{k_1,k_2,\dots ,k_d}{\omega }_{n_1}^{j_1{k}_1}{\omega }_{n_2}^{j_2{k}_2}\dots {\omega }_{n_d}^{j_d{k}_d}\\ & =\sum _{j_2=0}^{n_2-1}\sum _{j_3=0}^{n_3-1}\dots \sum _{j_d=0}^{n_d-1}{\omega }_{n_2}^{j_2{k}_2}\dots {\omega }_{n_d}^{j_d{k}_d}\left(\sum _{j_1=0}^{n_1-1}{a}_{k_1,k_2,\dots ,k_d}{\omega }_{n_1}^{j_1{k}_1}\right)\\ & =\sum _{j_2=0}^{n_2-1}\sum _{j_3=0}^{n_3-1}\dots \sum _{j_d=0}^{n_d-1}{\omega }_{n_2}^{j_2{k}_2}\dots {\omega }_{n_d}^{j_d{k}_d}\cdot a_{k_1,k_2,k_3,\dots ,k_d}^{\prime }\\ & =\sum _{j_2=0}^{n_2-1}\sum _{j_3=0}^{n_3-1}\dots \sum _{j_d=0}^{n_d-1}{a}_{k_1,k_2,k_3,\dots ,k_d}^{\prime }{\omega }_{n_2}^{j_2{k}_2}\dots {\omega }_{n_d}^{j_d{k}_d}\end{array}$

对于独立的 ${\displaystyle \frac{n}{n_1}}$ 个一维 DFT 问题 $(k_2,k_3,\dots ,k_d)$，将 $k_1$ 视作指数，那么最后一行的计算结果 $a^{\prime }:a_{\cdot ,k_2,k_3,\dots ,k_d}^{\prime }={\text{DFT}}_{n_1}(a_{\cdot ,k_2,k_3,\dots ,k_d}^{\prime })$，作为下一个问题的步骤的系数 $a$ 的输入，这个过程消去了一个求和符号。在下一次迭代中，仅有 ${\displaystyle \frac{n}{n_1{n}_2}}$ 个一维 DFT 问题（下一步是取原来第 $2$ 维），直到所有求和符号都被消去，最终得到的就是多维 DFT 的结果。

b

由于这 $d$ 个求和符号的上下限仅依赖于第 $d$ 维度 $n_d$，因此各个求和符号的位置可以随意改变次序；同样的，所有的 ${\omega }_n^{jk}$ 的次序都可以改变。因此，无论哪个维度的消去顺序都是一样的（可以把对应想消去的那一维放到第 $1$ 个位置，然后使用题目 30-2-a 的方法使用 FFT）。因此，原结论成立。

c

假设目前正在消去第 $i$ 维的求和符号，那么一共有 ${\displaystyle n/\prod _{j=1}^i{n}_j}$ 个 DFT 问题，这些 DFT 问题的规模大小为 $n_i$，需要花费 $O(n_i\lg n_i)$ 的时间求解，因此消去第 $i$ 维的求和符号所需要花费的时间为 ${\displaystyle n/\prod _{j=1}^i{n}_j\cdot O(n_i\lg n_i)=O(\left(n/\prod _{j=1}^{i-1}{n}_j\right)\lg n_i)}$。因此完成这 $d$ 步循环后，所需要花费的时间为

$\begin{array}{rl}\sum _{i=1}^d(\left(n/\prod _{j=1}^{i-1}{n}_j\right)\lg n_i)& \le n\lg n\cdot \sum _{i=1}^{d}1/\left(\prod _{j=1}^{i-1}{n}_i\right)\\ & \le n\lg n\cdot \sum _{i=1}^{d}1/\left(\prod _{j=1}^{i-1}2\right)(A)\\ & =n\lg n\cdot \sum _{i=1}^d{2}^{1-i}\\ & \le 2n\lg n\\ & =O(n\lg n)\end{array}$

其中步骤 $(A)$ 假定了 $n_i\ge 2$，因为如果 $n_i=1$，那么 $\lg n_i=0$，消去第 $i$ 个求和符号不需要花费任何时间。因此最终原结论成立。

30-3

a

当 $t\le n-1$ 时，有

$\begin{array}{rl}{A}^{(t)}(x)& ={\displaystyle \frac{d^t}{d{x}^t}}A(x)\\ & ={\displaystyle \frac{d^t}{d{x}^t}}\sum _{j=0}^{n-1}{b}_j(x-x_0{)}^j\\ & =\sum _{j=0}^{n-1}{\displaystyle \frac{d^t}{d{x}^t}}{b}_j(x-x_0{)}^j\\ & =\sum _{j=t}^{n-1}{\displaystyle \frac{d^t}{d{x}^t}}{b}_j(x-x_0{)}^j& (A)\\ & =\sum _{j=t}^{n-1}{\displaystyle \frac{j!}{(j-t)!}}{b}_j(x-x_0{)}^{j-t}\\ & =\sum _{j=0}^{n-1-t}{\displaystyle \frac{(j+t)!}{j!}}{b}_{j+t}(x-x_0{)}^j\end{array}$

步骤 $(A)$ 所得是因为所有小于 $t$ 次的多项式进行 $t$ 次求导后的值为 $0$。因此最终有 $A^{(t)}(x_0)=b_t\cdot t!$。

因此对于 $t=0,1,2,\dots ,n-1$，维护好 $t!$ 的值，就可以以 $O(n)$ 的时间计算出 $A^{(t)}(x_0)$ 的所有值。大概过程由程序 COMPUTE-ATX0 给出：

COMPUTE-ATX0(B, n, x)
  let D[0 : n - 1] be a new array
  fac = 1
  for t = 0 to n - 1
    D[t] = B[t] * fac
    fac = fac * (t + 1)
  return D

b

由于我们知道了值 ${\displaystyle A(x_0+{\omega }_n^k)=\sum _{j=0}^{n-1}{b}_j{\omega }_n^j}$，因此为了求出 $b_j$，只需要对 $A(x_0+{\omega }_n^k),k=0,1,\dots ,n-1$ 这 $n$ 个数进行一次逆向 FFT 即可，所需要花费的时间为 $O(n\lg n)$。

令示性函数 $i(x)=[x\ge 0]$。

c

$\begin{array}{rl}A(x_0+{\omega }_n^k)& =\sum _{j=0}^{n-1}{a}_j(x_0+{\omega }_n^k{)}^j\\ & =\sum _{j=0}^{n-1}{a}_j\sum _{r=0}^j{\displaystyle (\genfrac{}{}{0ex}{}{j}{r})}{\omega }_n^{kr}{x}_0^{j-r}\\ & =\sum _{j=0}^{n-1}{a}_j\sum _{r=0}^j{\displaystyle \frac{j!}{r!\cdot (j-r)!}}{\omega }_n^{kr}{x}_0^{j-r}\\ & =\sum _{j=0}^{n-1}{a}_j\sum _{r=0}^j{\displaystyle \frac{j!}{r!\cdot (j-r)!}}{\omega }_n^{kr}{x}_0^{j-r}\\ & =\sum _{j=0}^{n-1}{a}_j\sum _{r=0}^j{\displaystyle \frac{j!}{r!}}{\omega }_n^{kr}{\displaystyle \frac{x_0^{j-r}}{(j-r)!}}\\ & =\sum _{j=0}^{n-1}{a}_j(\sum _{r=0}^j{\displaystyle \frac{j!}{r!}}{\omega }_n^{kr}{\displaystyle \frac{x_0^{j-r}}{(j-r)!}}+\sum _{r=j+1}^{n-1}{\displaystyle \frac{j!}{r!}}{\omega }_n^{kr}\cdot 0)\\ & =\sum _{j=0}^{n-1}{a}_j(\sum _{r=0}^j{\displaystyle \frac{j!}{r!}}{\omega }_n^{kr}g(r-j)+\sum _{r=j+1}^{n-1}{\displaystyle \frac{j!}{r!}}{\omega }_n^{kr}g(r-j))\\ & =\sum _{j=0}^{n-1}{a}_j(\sum _{r=0}^{n-1}{\displaystyle \frac{j!}{r!}}{\omega }_n^{kr}g(r-j))\\ & =\sum _{r=0}^{n-1}\sum _{j=0}^{n-1}{a}_j\cdot {\displaystyle \frac{j!}{r!}}{\omega }_n^{kr}g(r-j)\\ & =\sum _{r=0}^{n-1}\sum _{j=0}^{n-1}{\displaystyle \frac{f(j)}{r!}}{\omega }_n^{kr}g(r-j)\\ & =\sum _{r=0}^{n-1}[{\displaystyle \frac{{\omega }_n^{kr}}{r!}}\sum _{j=0}^{n-1}f(j)g(r-j)]\end{array}$

因此最终原结论成立。

d

令 $h(j)=g(j-(n-1))$，那么有 ${\displaystyle A(x_0+{\omega }_n^k)=\sum _{r=0}^{n-1}[{\displaystyle \frac{{\omega }_n^{kr}}{r!}}\sum _{j=0}^{n-1}f(j)h(n+r-1-j)]}$，然而对于 $j\ge n$，都有 $h(j)=0$。

当 $j\ge n$ 时，假设 $f(j)=0$，令 ${\displaystyle y_r=\sum _{j=0}^{n-1}f(j)h(n+r-1-j)=\sum _{j=0}^{n+r-1}f(j)h(n+r-1-j)}$，那么可以在 $O(n\lg n)$ 的时间内通过多项式卷积计算出 $y_r$，其中 $r\in [0,n)$。

令 $z_r={\displaystyle \frac{y_r}{r!}}$，那么得到 ${\displaystyle A(x_0+{\omega }_n^k)=\sum _{r=0}^{n-1}{z}_r{\omega }_n^{kr}}$。接下来再使用一次 FFT 即可计算出 $A(x_0+{\omega }_n^k)$，其中 $k\in [0,n)$。

然后，按照题目 30-3-b 的结论，使用一次逆向 FFT，得到多项式 $A$ 的系数 $b_0,b_1,\dots ,b_{n-1}$。

最后使用题目 30-3-a 的结论，通过系数 $b$ 在 $O(n)$ 的时间内计算出 $A(x)$ 所有非平凡导数在 $x_0$ 的值。由于整个过程仅仅使用了 $5$ 次 FFT，以及最后一步以 $O(n)$ 的时间计算出所有答案，因此整个过程的时间复杂度为 $O(n\lg n)$。

整个大致过程由 COMPUTE-DERIVATIVE-BY-FFT 给出。

COMPUTE-DERIVATIVE-BY-FFT(A, n, x)
  m = 2 ^ (⌈lg n⌉ + 1)
  for i = 1 to m - n
    INSERT(A, 0)
  let F[0 : m - 1], H[0 : m - 1] ,fac[0, m - 1] be new arrays
  fac[0] = 1
  for i = 1 to n - 1
    fac[i] = fac[i - 1] * i
  for i = 0 to n - 1
    F[i] = A[i] * fac[i]
    l = i - (n - 1)
    H[i] = exp(x, -l) / fac[-l]
  Y = FFT-INV(FFT(F, m) ⋅ FFT(H, m), m)
  let Z[0 : m - 1], D[0 : n - 1] be new arrays
  for i = 0 to n - 1
    Z[i] = Y[i + m / 2] / fac[i]
  B = FFT-INV(Z, m)
  for i = 0 to n - 1
    D[i] = B[i] * fac[i]
  return 0

30-4

a

这个问题等价于证明：$x-z\mid A(x)-A(z)$。

首先证明一个引理：$\mathrm{\forall }n\ge 1$，其中 $n$ 是一个整数，都有 $a-b\mid a^n-b^n$。接下来使用归纳法进行证明。当 $n=1$ 时，明显成立。当 $n>1$ 时，假设对于 $k=1,2,\dots ,n-1$，都有 $a-b\mid a^k-b^k$。考虑 $a^n-b^n$，那么有 $a^n-b^n=(a-b)\cdot a^{n-1}+b(a^{n-1}-b^{n-1})$。由于前者包含一个因子 $(a-b)$，因此 $a-b$ 整除 $(a-b)\cdot a^{n-1}$；按照假设，可知 $a-b\mid b(a^{n-1}-b^{n-1})$，因此得出 $a-b\mid a^n-b^n$，该引理成立。

接下来证明原结论。考虑 $A(x)-A(z)$，那么有 ${\displaystyle A(x)-A(z)=\sum _{i=0}^{n-1}{a}_i(x^i-z^i)}$。当 $i=0$ 时，这个项为 $0$；对于 $i>0$，按照上面的引理，都有 $x-z\mid x^i-z^i$，因此最终有 $x-z\mid A(x)-A(z)$。即

$$A(x)mod(x-z)=A(z)$$

b

可以得知 $Q_{kk}(x)=A(x)mod(x-x_k)$，因此按照题目 30-4-a 的结论，有 $Q_{kk}(x)=A(x_k)$。

由于多项式 $P_{0,n-1}(x)$ 的次数为 $n$，但是 $A(x)$ 的次数为 $n-1$，因此 $A(x)mod{P}_{0,n-1}(x)=A(x)$，即 $Q_{0,n-1}(x)=A(x)$。

c

本题考虑证明一个更强的结论：对于任意非空集合 $S\subseteq \{0,1,\dots ,n-1\}$ 的任意一个非空子集 $T$，都有 ${\displaystyle A(x)mod\prod _{i\in T}(x-x_i)=(A(x)mod\prod _{i\in S}(x-x_i))mod\prod _{i\in T}(x-x_i)}$。

令 ${\displaystyle s(x)=\prod _{i\in S}(x-x_i),t(x)=\prod _{i\in T}(x-x_i)}$，可见 $t(x)\mid s(x)$。接下里是证明：构造两个多项式 $q_1(x),r_1(x_1)$ 满足 ${\displaystyle A(x)=q_1(x)\cdot s(x)+r_1(x)}$，其中 $\text{degree}(r_1)<|S|$，那么有 $A(x)mods(x)=r_1(x)$。同时构造两个多项式 $q_2(x),r_2(x)$ 满足 $r_1(x)=q_2(x)\cdot t(x)+r_2(x)$，其中 $\text{degree}(r_2)<|T|$。由于 $t(x)\mid s(x)$，令多项式 $u(x)=s(x)/t(x)$，那么有

$\begin{array}{rl}A(x)& =q_1(x)\cdot s(x)+r_1(x)\\ & =q_1(x)\cdot u(x)\cdot t(x)+q_2(x)\cdot t(x)+r_2(x)\\ & =(q_1(x)\cdot u(x)+q_2(x))\cdot t(x)+r_2(x)\end{array}$

由于 $\text{degree}(r_2)<|T|$，因此有 $A(x)modt(x)=r_2(x)$，上面证明的结论成立。

假设现在 $S=\{i,i+1,\dots ,j\}$。当 $T=\{i,i+1,\dots ,k\}$ 时，则相当于证明了 $A(x)mod{P}_{ik}(x)=(A(x)mod{P}_{ij}(x))mod{P}_{ik}(x)$，即 $Q_{ik}(x)=Q_{ij}(x)mod{P}_{ik}(x)$。当 $T=\{k,k+1,\dots ,j\}$ 时，则相当于证明了 $A(x)mod{P}_{kj}(x)=(A(x)mod{P}_{ij}(x))mod{P}_{kj}(x)$，即 $Q_{kj}(x)=Q_{ij}(x)mod{P}_{kj}(x)$，因此原结论成立。

d

令 $m=2^{\lceil \lg n\rceil }$。整个过程分为两个阶段。按照题目 30.2-7 的思路，首先自底向上，使用 FFT 计算出所有的 $P_{lr}:\mathrm{\exists }k:r-l+1=2^k,2^k\mid l$，这个阶段将花费 $O(m{\lg }^{2}m)$ 的时间。接下来则是自顶向下计算出所有的 $Q_{lr}:\mathrm{\exists }k:r-l+1=2^k,2^k\mid l$，同样的，在第 $k$ 轮迭代中计算单次多项式的长度为 ${\displaystyle \frac{m}{2^{k-1}}}$，取模所需要花费的时间为 $O({\displaystyle \frac{m}{2^{k-1}}}\lg {\displaystyle \frac{m}{2^{k-1}}})$。一共需要进行 $2^{k-1}\cdot 2$ 次，因此总共所需要花费的时间为 $O(m\lg m)$。因此第二个阶段也将花费 $O(m{\lg }^{2}m)$ 的时间。

由于两个阶段都使用了 $O(m{\lg }^{2}m)$ 的运行时间，并且 $n=\mathrm{\Theta }(m)$，因此这个算法的时间复杂度为 $O(n{\lg }^{2}n)$，具体过程由 EVALUATE-N-VALUES 给出。

// 假设函数PLOY-MULTIPLY和POLY-MODULO会将多项式的长度拓展成2的幂，并且用FFT和FFT-INV分别作为子程序运行，以O(n lg n)的时间进行，这里忽略了实现细节。
EVALUATE-N-VALUES(A, X, n)
  m = 2 ^ (⌈lg n⌉)
  c = ⌈lg n⌉
  for i = 0 to m
    if i < n
      P_{ii} = [-X[i], 1]
    else
      P_{ii} = [1, 0]
  for k = 1 to c
    for l = 0 to m by 2^k
      r = l + 2 ^ k - 1
      P_{l, r} = PLOY-MULTIPLY(P_{l, l + 2 ^ (k - 1) - 1}, P_{l + 2 ^ (k - 1), r})
  Q_{0, m - 1} = A
  for k = c to 1
    for l = 0 to m by 2^k
      r = l + 2 ^ k - 1
      Q_{l, l + 2 ^ (k - 1) - 1} = PLOY-MODULO(Q_{l, r}, P_{l + 2 ^ (k - 1), r})
      Q_{l + 2 ^ (k - 1), r} = PLOY-MODULO(Q_{l, r}, P_{l, l + 2 ^ (k - 1) - 1})
  let Y[0 : n - 1] be a new array
  for i = 0 to n - 1
    Y[i] = Q_{ii}
  return Y

30-5

事实上，这种在 ${\mathbb{Z}}_p$ 上的傅里叶变换称为数论变换。

a

按照素数定理，从 $1$ 到 $m$ 中素数的个数占比约为 ${\displaystyle \frac{1}{\ln m}}$。因此从 $1$ 到 $n\ln n$ 中选取到一个质数的概率约为 ${\displaystyle \frac{1}{\ln n+\ln \ln n}}\approx {\displaystyle \frac{1}{\ln n}}$。考虑从 $k=1,2,3,\dots ,\ln n$，考察存在 $k$ 使得 $kn+1$ 是一个质数的概率 $p$。可以计算得到

$\begin{array}{rl}p& \approx 1-{(1-{\displaystyle \frac{1}{\ln n+\ln \ln n}})}^{\ln n}\\ & \approx 1-{(1-{\displaystyle \frac{1}{\ln n}})}^{\ln n}\\ & >1-{\displaystyle \frac{1}{e}}\\ & \approx 0.632121\end{array}$

因此，有相当高的概率使得这 $\ln n$ 数中存在一个质数，因此需要检查的 $k$ 期望个数为 $O(\lg n)$。因此 $p$ 的期望值为 $O(n\lg n)$，并且 $p$ 的长度值的期望是 $O(\lg (n\lg n))=O(\lg n+\lg \lg n)=O(\lg n)$。

b

由于 $g$ 是 ${\mathbb{Z}}_p^{\ast }$ 生成元，因此 $g$ 在 ${\mathbb{Z}}_p^{\ast }$ 上的阶 ${\lambda }_p(g)=p-1=kn$。由于 $w=g^{k}modp$，因此 ${\lambda }_p(w)=n$。也就是说，${\mathbb{Z}}_p^{\ast }$ 上的一个循环子群 $⟨w⟩$ 的大小为 $n$。按照 ${\omega }_n$ 的定义，有 ${\omega }_n^n=1$，类似的，按照费马小定理，有 $w^n\equiv (g^k{)}^n\equiv g^{p-1}\equiv 1(\mathrm{mod}p)$。

接下来证明引理 / 定理 / 推论 30.3，30.4，30.5，30.6, 30.76 在 $⟨w⟩$ 中是成立的。

引理 30.3 的证明：考虑 $n$ 的某个因子 $d$，令 $w^{\prime }=w^d$，那么有 $w^{\prime k/d}\equiv (w^d{)}^{k/d}\equiv w^k(\mathrm{mod}p)$，因此原结论成立。

推论 30.4 的证明：不难知道 $w^{n/2}\equiv g^{kn/2}\equiv -1(\mathrm{mod}p)$，（由于 $g^{kn}\equiv 1(\mathrm{mod}p)$，因此 $g^{kn/2}modp$ 的值要么为 $-1$，要么为 $1$，但是它的值必定是 $-1$，因为 $g$ 是原根）。

引理 30.5 的证明：$(w^{k+n/2}{)}^2\equiv w^{2k+n}\equiv w^{2k}\cdot w^n\equiv (w^k{)}^2(\mathrm{mod}p)$，因此结论得证。

引理 30.6 的证明：当 $n\nmid k$ 时，有 $w^k\not\equiv 1(\mathrm{mod}p)$ 成立。证明过程和原本的定理 30.6 的计算过程一致，原结论得证。

定理 30.7 的证明：此时 $V_n^{-1}$ 的第 $j$ 行第 $k$ 列的项为 $w^{-jk}\cdot n^{-1}modp$。由于 $p$ 是奇数，且 $n<p$，因此 $gcd(n,p)=1$，因此在 ${\mathbb{Z}}_p$ 中存在 $n$ 的逆元 $n^{-1}$，结论中的写法是成立的，考虑 $[V_n^{-1}{V}_n{]}_{kk}$ 的值，有 $[V_n^{-1}{V}_n{]}_{kk}\equiv {\displaystyle \sum _{j=0}^{n-1}(w^{-jk}\cdot n^{-1})(w^{j{k}^{\prime }})\equiv n^{-1}\cdot \sum _{j=0}^{n-1}{w}^{j(k^{\prime }-k)}(\mathrm{mod}p)}$。其余证明过程类似，因此原结论成立。

那么在 ${\mathbb{Z}}_p$ 上的 DFT 问题定义为：给定长度为 $n$ 的序列 $(a_0,a_1,\dots ,a_{n-1})$，计算 ${\displaystyle y_j=\sum _{i=0}^{n-1}{a}_i(w^j{)}^{i}modp}$，其中 $w=g^k$。最终，计算结果 $y_j\in {\mathbb{Z}}_p$，可见计算结果是封闭的。正向 DFT 的过程成立。

现在在 ${\mathbb{Z}}_p$ 上的逆向 DFT 问题定义为：给定长度为 $n$ 的序列 $(y_0,y_1,\dots ,y_{n-1})$，构造一组序列 $(a_0,a_1,\dots ,a_{n-1})\in {\mathbb{Z}}_p^n$，使得 ${\displaystyle \mathrm{\forall }j\in [0,n),y_j=\sum _{i=0}^{n-1}{a}_i(w^j{)}^{i}modp}$ 均成立，其中 $w=g^k$。那么按照类似的结论，由于 $gcd(w,p)=1$，因此 $w$ 在 ${\mathbb{Z}}_p^{\ast }$ 中也存在逆元 $w^{-1}$。容易验证 $⟨w⟩=⟨w^{-1}⟩$，因此 ${\displaystyle a_k=n^{-1}\sum _{i=0}^{n-1}{y}_i({\omega }^{-k}{)}^{i}modp}$ 的整个计算过程是封闭的，即 DFT 的逆过程是正确定义的。

c

对 FFT 和 FFT-INV 改造后，可以得到 FFT-OVER-RING 和 FFT-INV-OVER-RING 算法，程序如下给出。由于操作分别和 FFT 与 FFT-INV 一致，因此其时间复杂度均为 $O(n\lg n)$。需要注意的是，$w^{-1}$ 和 $n^{-1}$ 可以提前计算好，避免以后的重复计算。

FFT-OVER-RING(a, n, p, wn)
  if n == 1
    return a
  w = 1
  a-even = (a_0, a_2, ..., a_{n - 2})
  a-odd = (a_1, a_3, ..., a_{n - 1})
  y-even = FFT-INV(FFT-OVER-RING, n / 2, p, wn * wn % p)
  y-odd = FFT-INV(FFT-OVER-RING, n / 2, wn * wn % p)
  for k = 0 to n / 2 - 1
    y_k = (a-even_{k} + w * a-odd_{k}) % p
    y_{k + n / 2} = (a-even_{k} - w * a-odd_{k}) % p
    w = w * wn % p
  return y

// wn^{-1}和n^{-1}需要提前使用扩展欧几里得算法计算好，避免重复计算，结果分别用wn-inv和n-inv表示。
FFT-INV-OVER-RING(y, n, p, wn-inv)
  if n == 1
    return a
  w = 1
  y-even = (y_0, y_2, ..., y_{n - 2})
  y-odd = (y_1, y_3, ..., y_{n - 1})
  a-even = FFT-INV-OVER-RING(y-even, n / 2, p, wn-inv * wn-inv % p)
  a-odd = FFT-INV-OVER-RING(y-odd, n / 2, p, wn-inv * wn-inv % p)
  for k = 0 to n / 2 - 1
    a_k = (a-even_{k} + w * a-odd_{k}) * n-inv % p
    a_{k + n / 2} = (a-even_{k} - w * a-odd_{k}) * n-inv % p
    w = w * wn-inv % p
  return a

d

由于 $n=8$，因此 $g_n=g^{\frac{p-1}{n}}=9$。

那么 $\mathrm{\forall }k\in [0,n)$，都有 ${\displaystyle y_k=\sum _{i=0}^{n-1}{a}_i\cdot (g_n^k{)}^{i}modp}$。可以计算得到

$\begin{array}{rl}{y}_0& =\sum _{i=0}^{n-1}{a}_i\cdot (g_n^0{)}^{i}modp=14\\ y_1& =\sum _{i=0}^{n-1}{a}_i\cdot (g_n^1{)}^{i}modp=10\\ y_2& =\sum _{i=0}^{n-1}{a}_i\cdot (g_n^2{)}^{i}modp=10\\ y_3& =\sum _{i=0}^{n-1}{a}_i\cdot (g_n^3{)}^{i}modp=4\\ y_4& =\sum _{i=0}^{n-1}{a}_i\cdot (g_n^4{)}^{i}modp=8\\ y_5& =\sum _{i=0}^{n-1}{a}_i\cdot (g_n^5{)}^{i}modp=11\\ y_6& =\sum _{i=0}^{n-1}{a}_i\cdot (g_n^6{)}^{i}modp=13\\ y_7& =\sum _{i=0}^{n-1}{a}_i\cdot (g_n^7{)}^{i}modp=15\end{array}$

因此 DFT 的结果为 $(14,10,10,4,8,11,13,15)$。