算法导论30 Problems 答案

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{A_1(x)=\sum_{i=0}^{n/2-1} a_ix^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_ix^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)\)的递推式：

\[T(n)=3T(n/2)+\Theta(n)\]

根据主定理的第1个条件，可以得到\(T(n)=\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{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)\)（即常数）的比特操作。

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_{n_3}^{j_3k_3},\dots,\omega_{n_d}^{j_dk_d}\)都视为是常数。那么有

\(\begin{aligned} 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_1k_1}\omega_{n_2}^{j_2k_2}\dots\omega_{n_d}^{j_dk_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_1k_1}\omega_{n_2}^{j_2k_2}\dots\omega_{n_d}^{j_dk_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_1k_1}\omega_{n_2}^{j_2k_2}\dots\omega_{n_d}^{j_dk_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_2k_2}\dots\omega_{n_d}^{j_dk_d}\left(\sum_{j_1=0}^{n_1-1}a_{k_1,k_2,\dots,k_d}\omega_{n_1}^{j_1k_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_2k_2}\dots\omega_{n_d}^{j_dk_d}\cdot a'_{k_1,k_2,k_3,\dots,k_d}\\ &=\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}\omega_{n_2}^{j_2k_2}\dots\omega_{n_d}^{j_dk_d}\\ \end{aligned}\)

对于独立的\(\dfrac{n}{n_1}\)个一维DFT问题\((k_2,k_3,\dots,k_d)\)，将\(k_1\)视作指数，那么最后一行的计算结果\(a':a'_{\cdot,k_2,k_3,\dots,k_d}=\text{DFT}_{n_1}(a'_{\cdot,k_2,k_3,\dots,k_d})\)，作为下一个问题的步骤的系数\(a\)的输入，这个过程消去了一个求和符号。在下一次迭代中，仅有\(\dfrac{n}{n_1n_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(\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} n_j\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}b_j(x-x_0)^{j}\\ &=\sum_{j=t}^{n-1}\dfrac{d^t}{dx^t}b_j(x-x_0)^{j}&\qquad(A)\\ &=\sum_{j=t}^{n-1}\dfrac{j!}{(j-t)!}b_j(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给出：

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\ge0]\)。

c

\(\begin{aligned} 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\dbinom{j}{r}\omega_n^{kr}x_0^{j-r}\\ &=\sum_{j=0}^{n-1} a_j\sum_{r=0}^j\dfrac{j!}{r!\cdot(j-r)!}\omega_n^{kr}x_0^{j-r}\\ &=\sum_{j=0}^{n-1} a_j\sum_{r=0}^j\dfrac{j!}{r!\cdot(j-r)!}\omega_n^{kr}x_0^{j-r}\\ &=\sum_{j=0}^{n-1} a_j\sum_{r=0}^j\dfrac{j!}{r!}\omega_n^{kr}\dfrac{x_0^{j-r}}{(j-r)!}\\ &=\sum_{j=0}^{n-1} a_j\left(\sum_{r=0}^j\dfrac{j!}{r!}\omega_n^{kr}\dfrac{x_0^{j-r}}{(j-r)!}+\sum_{r=j+1}^{n-1}\dfrac{j!}{r!}\omega_n^{kr}\cdot 0\right)\\ &=\sum_{j=0}^{n-1} a_j\left(\sum_{r=0}^j\dfrac{j!}{r!}\omega_n^{kr}g(r-j)+\sum_{r=j+1}^{n-1}\dfrac{j!}{r!}\omega_n^{kr} g(r-j)\right)\\ &=\sum_{j=0}^{n-1} a_j\left(\sum_{r=0}^{n-1}\dfrac{j!}{r!}\omega_n^{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{\omega_n^{kr}}{r!}\sum_{j=0}^{n-1}f(j)g(r-j)\right]\\ \end{aligned}\)

因此最终原结论成立。

d

令\(h(j)=g(j-(n-1))\)，那么有\(\displaystyle{A(x_0+\omega_n^k)=\sum_{r=0}^{n-1}\left[\dfrac{\omega_n^{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{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=\dfrac{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)\)。

首先证明一个引理：\(\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)\bmod (x-z)=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-x_i))\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给出。

// 假设函数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}V_n]_{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{y_j=\sum_{i=0}^{n-1}} a_i(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})\)，构造一组序列\((a_0,a_1,\dots,a_{n-1})\in\mathbb{Z}_p^n\)，使得\(\displaystyle{\forall j\in[0,n),y_j=\sum_{i=0}^{n-1}} a_i(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}\)可以提前计算好，避免以后的重复计算。

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{y_k=\sum_{i=0}^{n-1} a_i\cdot (g_n^k)^i\bmod p}\)。可以计算得到

\(\begin{aligned} y_0&=\sum_{i=0}^{n-1} a_i\cdot (g_n^0)^i\bmod p=14\\ y_1&=\sum_{i=0}^{n-1} a_i\cdot (g_n^1)^i\bmod p=10\\ y_2&=\sum_{i=0}^{n-1} a_i\cdot (g_n^2)^i\bmod p=10\\ y_3&=\sum_{i=0}^{n-1} a_i\cdot (g_n^3)^i\bmod p=4\\ y_4&=\sum_{i=0}^{n-1} a_i\cdot (g_n^4)^i\bmod p=8\\ y_5&=\sum_{i=0}^{n-1} a_i\cdot (g_n^5)^i\bmod p=11\\ y_6&=\sum_{i=0}^{n-1} a_i\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)\)。