算法导论30 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 12k 阅读时长 ≈ 11 分钟

30-1

a

本题和题目4.2-5类似。

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

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

b

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

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

令$\displaystyle{A1(x)=\sum{i=0}^{n/2-1} aix^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} bix^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{aligned}
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{aligned}$

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

$\begin{aligned}
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{aligned}$

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

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

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

令$\displaystyle{A1(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{aligned}
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{aligned}$

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

$\begin{aligned}
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{aligned}$

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

c

先将$n$位二进制数$a,b$在$O(n)$的时间内转化成度数为$n$的多项式$\displaystyle{A(x)=\sum{i=0}^{n-1} a_ix^i,B(x)=\sum{i=0}^{n-1} b_ix^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)$（即常数）的比特操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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_2k_2},\omega{n3}^{j_3k_3},\dots,\omega{n_d}^{j_dk_d}$都视为是常数。那么有

$\begin{aligned}
y{k_1,k_2,\dots,k_d}&=\sum{j1=0}^{n_1-1}\sum{j2=0}^{n_2-1}\dots\sum{jd=0}^{n_d-1}a{k1,k_2,\dots,k_d}\omega{n1}^{j_1k_1}\omega{n2}^{j_2k_2}\dots\omega{nd}^{j_dk_d}\
&=\sum{j2=0}^{n_2-1}\sum{j3=0}^{n_3-1}\dots\sum{jd=0}^{n_d-1}\sum{j1=0}^{n_1-1}a{k1,k_2,\dots,k_d}\omega{n1}^{j_1k_1}\omega{n2}^{j_2k_2}\dots\omega{nd}^{j_dk_d}\
&=\sum{j2=0}^{n_2-1}\sum{j3=0}^{n_3-1}\dots\sum{jd=0}^{n_d-1}\sum{j1=0}^{n_1-1}a{k1,k_2,\dots,k_d}\omega{n1}^{j_1k_1}\omega{n2}^{j_2k_2}\dots\omega{nd}^{j_dk_d}\
&=\sum{j2=0}^{n_2-1}\sum{j3=0}^{n_3-1}\dots\sum{jd=0}^{n_d-1}\omega{n2}^{j_2k_2}\dots\omega{nd}^{j_dk_d}\left(\sum{j1=0}^{n_1-1}a{k1,k_2,\dots,k_d}\omega{n1}^{j_1k_1}\right)\
&=\sum{j2=0}^{n_2-1}\sum{j3=0}^{n_3-1}\dots\sum{jd=0}^{n_d-1}\omega{n2}^{j_2k_2}\dots\omega{nd}^{j_dk_d}\cdot a’{k1,k_2,k_3,\dots,k_d}\
&=\sum{j2=0}^{n_2-1}\sum{j3=0}^{n_3-1}\dots\sum{jd=0}^{n_d-1}a’{k1,k_2,k_3,\dots,k_d}\omega{n2}^{j_2k_2}\dots\omega{n_d}^{j_dk_d}\
\end{aligned}$

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

b

由于这$d$个求和符号的上下限仅依赖于第$d$维度$nd$，因此各个求和符号的位置可以随意改变次序；同样的，所有的$\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} nj\cdot O(n_i\lg n_i)=O\left(\left(n/\prod{j=1}^{i-1} n_j\right)\lg n_i\right)}$。因此完成这$d$步循环后，所需要花费的时间为

$\begin{aligned}
\sum{i=1}^d \left(\left(n/\prod{j=1}^{i-1} nj\right)\lg n_i\right)&\le n\lg n\cdot \sum{i=1}^d1/\left(\prod{j=1}^{i-1} n_i\right)\
&\le n\lg n\cdot \sum{i=1}^d1/\left(\prod{j=1}^{i-1} 2\right)\qquad(A)\
&=n\lg n\cdot \sum{i=1}^d 2^{1-i}\
&\le 2n\lg n\
&=O(n\lg n)
\end{aligned}$

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

30-3

a

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

$\begin{aligned}
A^{(t)}(x)&=\dfrac{d^t}{dx^t}A(x)\
&=\dfrac{d^t}{dx^t}\sum{j=0}^{n-1}b_j(x-x_0)^{j}\
&=\sum{j=0}^{n-1}\dfrac{d^t}{dx^t}bj(x-x_0)^{j}\
&=\sum{j=t}^{n-1}\dfrac{d^t}{dx^t}bj(x-x_0)^{j}&\qquad(A)\
&=\sum{j=t}^{n-1}\dfrac{j!}{(j-t)!}bj(x-x_0)^{j-t}\
&=\sum{j=0}^{n-1-t}\dfrac{(j+t)!}{j!}b_{j+t}(x-x_0)^{j}\
\end{aligned}$

步骤$(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给出：

1
2
3
4
5
6
7
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(x0+\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\ge0]$。

c

$\begin{aligned}
A(x0+\omega_n^k)&=\sum{j=0}^{n-1} aj(x_0+\omega_n^k)^j\
&=\sum{j=0}^{n-1} aj\sum{r=0}^j\dbinom{j}{r}\omegan^{kr}x_0^{j-r}\
&=\sum{j=0}^{n-1} aj\sum{r=0}^j\dfrac{j!}{r!\cdot(j-r)!}\omegan^{kr}x_0^{j-r}\
&=\sum{j=0}^{n-1} aj\sum{r=0}^j\dfrac{j!}{r!\cdot(j-r)!}\omegan^{kr}x_0^{j-r}\
&=\sum{j=0}^{n-1} aj\sum{r=0}^j\dfrac{j!}{r!}\omegan^{kr}\dfrac{x_0^{j-r}}{(j-r)!}\
&=\sum{j=0}^{n-1} aj\left(\sum{r=0}^j\dfrac{j!}{r!}\omegan^{kr}\dfrac{x_0^{j-r}}{(j-r)!}+\sum{r=j+1}^{n-1}\dfrac{j!}{r!}\omegan^{kr}\cdot 0\right)\
&=\sum{j=0}^{n-1} aj\left(\sum{r=0}^j\dfrac{j!}{r!}\omegan^{kr}g(r-j)+\sum{r=j+1}^{n-1}\dfrac{j!}{r!}\omegan^{kr} g(r-j)\right)\
&=\sum{j=0}^{n-1} aj\left(\sum{r=0}^{n-1}\dfrac{j!}{r!}\omegan^{kr}g(r-j)\right)\
&=\sum{r=0}^{n-1} \sum{j=0}^{n-1}a_j\cdot\dfrac{j!}{r!}\omega_n^{kr}g(r-j)\
&=\sum{r=0}^{n-1} \sum{j=0}^{n-1}\dfrac{f(j)}{r!}\omega_n^{kr}g(r-j)\
&=\sum{r=0}^{n-1}\left[\dfrac{\omegan^{kr}}{r!}\sum{j=0}^{n-1}f(j)g(r-j)\right]\
\end{aligned}$

因此最终原结论成立。

d

令$h(j)=g(j-(n-1))$，那么有$\displaystyle{A(x0+\omega_n^k)=\sum{r=0}^{n-1}\left[\dfrac{\omegan^{kr}}{r!}\sum{j=0}^{n-1}f(j)h(n+r-1-j)\right]}$，然而对于$j\ge n$，都有$h(j)=0$。

当$j\ge n$时，假设$f(j)=0$，令$\displaystyle{yr=\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)$。

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

然后，按照题目30-3-b的结论，使用一次逆向FFT，得到多项式$A$的系数$b0,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给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)$。

首先证明一个引理：$\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)$。即

b

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

由于多项式$P{0,n-1}(x)$的次数为$n$，但是$A(x)$的次数为$n-1$，因此$A(x)\bmod 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)\bmod \prod{i\in T}(x-x_i)=(A(x)\bmod \prod{i\in S}(x-xi))\bmod
\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)\bmod s(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{aligned}
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{aligned}$

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

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

d

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 假设函数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$中素数的个数占比约为$\dfrac{1}{\ln m}$。因此从$1$到$n\ln n$中选取到一个质数的概率约为$\dfrac{1}{\ln n+\ln \ln n}\approx\dfrac{1}{\ln n}$。考虑从$k=1,2,3,\dots,\ln n$，考察存在$k$使得$kn+1$是一个质数的概率$p$。可以计算得到

$\begin{aligned}
p&\approx 1-\left(1-\dfrac{1}{\ln n+\ln\ln n}\right)^{\ln n}\
&\approx1-\left(1-\dfrac{1}{\ln n}\right)^{\ln n}\
&> 1-\dfrac{1}{e}\
&\approx 0.632121
\end{aligned}$

因此，有相当高的概率使得这$\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\bmod p$，因此$\lambda_p(w)=n$。也就是说，$\mathbb{Z}_p^{\ast}$上的一个循环子群$\langle w\rangle$的大小为$n$。按照$\omega_n$的定义，有$\omega_n^n=1$，类似的，按照费马小定理，有$w^{n}\equiv (g^{k})^n\equiv g^{p-1}\equiv 1\pmod p$。

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

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

推论30.4的证明：不难知道$w^{n/2}\equiv g^{kn/2}\equiv -1\pmod {p}$，（由于$g^{kn}\equiv 1\pmod p$，因此$g^{kn/2} \bmod p$的值要么为$-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\pmod p$，因此结论得证。

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

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

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

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

c

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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$。

那么$\forall k\in [0,n)$，都有$\displaystyle{yk=\sum{i=0}^{n-1} a_i\cdot (g_n^k)^i\bmod p}$。可以计算得到

$\begin{aligned}
y0&=\sum{i=0}^{n-1} ai\cdot (g_n^0)^i\bmod p=14\
y_1&=\sum{i=0}^{n-1} ai\cdot (g_n^1)^i\bmod p=10\
y_2&=\sum{i=0}^{n-1} ai\cdot (g_n^2)^i\bmod p=10\
y_3&=\sum{i=0}^{n-1} ai\cdot (g_n^3)^i\bmod p=4\
y_4&=\sum{i=0}^{n-1} ai\cdot (g_n^4)^i\bmod p=8\
y_5&=\sum{i=0}^{n-1} ai\cdot (g_n^5)^i\bmod p=11\
y_6&=\sum{i=0}^{n-1} ai\cdot (g_n^6)^i\bmod p=13\
y_7&=\sum{i=0}^{n-1} a_i\cdot (g_n^7)^i\bmod p=15\
\end{aligned}$

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