算法导论31 Problems 答案

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

31-1

a

通过推论31.4可知，由于\(a,b\)是偶数，因此可以写成\(a'=a/2,b'=a/2\)。代入\(n=2\)的情形，即可得到

\(\gcd(a,b)=\gcd(2a',2b')=2\gcd(a',b')=2\gcd(a/2,b/2)\)

b

当\(a\)是奇数，\(b\)是奇数时，由于\(2\mid b,2\nmid a\)，因此\(d=\gcd(a,b)\)不满足\(2\mid d\)，因此对\(b\)抛弃质因子\(2\)，仍然不会对\(d\)值造成任何影响。故\(\gcd(a,b)=\gcd(a,b/2)\)。

c

我们首先证明：\(\gcd(a,b)=\gcd(a-b,b)\)。证明方式与定理31.9类似。

令\(d=\gcd(a,b)\)，那么\(d\mid a,d\mid b\)。根据式子31.4，有\(d\mid (a-b)\)。

因此有\(\gcd(a,b)\mid \gcd(a-b,b)\)。

类似的，令\(d'=\gcd(a-b,b)\)，那么有\(d'\mid (a-b),d'\mid b\)。可以将\(a\)写成\(a=1\cdot(a-b)+1\cdot b\)。根据式子31.4，有\(d'\mid a\)。

因此，\(\gcd(a-b,b)\mid\gcd(a,b)\)，这说明\(\gcd(a,b)=\gcd(a-b,b)\)。

此时\(a-b\)是偶数，\(b\)是奇数，根据题目33-1-b的结论，有\(\gcd(a-b,b)=\gcd((a-b)/2,b)\)。

因此最终得到\(\gcd(a,b)=\gcd((a-b)/2,b)\)。

d

这个算法由程序GCD'给出。经过一轮迭代后，两个参数之和\(a+b\)的值至多是原来的\(\dfrac{3}{4}\)。因此，这个程序的时间复杂度为\(O(\lg (a+b))=O(\lg a)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
GCD'(a, b)
  if a > b
    exchange a with b
  if b == 0
    return a
  // 取a, b的奇偶性
  (x, y) = (a & 1, b & 1)
  if x == 1 and y == 1
    return GCD'((a - b) >> 1, b)
  else if x == 1
    return GCD'(a, b >> 1)
  else if y == 1
    return GCD'(a >> 1, b)
  else
    return GCD'(a >> 1, b >> 1) << 1

31-2

将\(a\)和\(b\)表示成一个二进制数，然后使用长除法求解\(a,b\)。

由于商有\(O(\lg q)\)位，因此需要进行\(O(\lg q)\)的迭代，每轮迭代求出商的一位数值。每一轮中，需要判断当前商位的前\(\lg b\)比特所表示的数是否大于等于\(b\)；如果大于等于\(b\)，那么需要做一次\(\lg b\)位数的减法，商的这一位为\(1\)，并补上后一位数；否则什么都不做，直接补上后一位数，商的这一位为\(0\)。无论是比较操作还是减法操作都需要花费\(O(\lg b)\)次比特操作进行。因此在整个迭代过程中共进行了\(O(\lg q\lg b)\)次比特操作。

此外，还需要\(O(\lg b)\)的时间来找到商的最高位。

最终，因此整个操作需要\(O((1+\lg q)\lg b)\)次的位操作。

b

将计算\(\gcd(a,b)\)转化为求解\(\gcd(b,a\bmod b)\)这个过程本质上是进行了一次取模操作。因此只需要证明这个上界值超过\(O((1+\lg q)\lg b)\)即可。

\(\begin{aligned} c(\mu(a,b)-\mu(b,a\bmod b))&=c(\mu(a,b)-\mu(b,r))\\ &=c((1+\lg a)(1+\lg b)-(1+\lg b)(1+\lg r))\\ &=c(1+\lg b)(\lg a-\lg r)\\ &\ge c(1+\lg b)(\lg a-\lg b)\\ &\ge c/2(1+\lg b)(1+\lg q)&\qquad(A)\\ &\ge c/2(1+\lg q) \lg b \end{aligned}\) 其中步骤\((A)\)假设了\(c\)足够大。通过缩减系数，来保证\(\lg q+1>\lg a-\lg b\)所产生的差值不受影响。

因此，只要\(c\)足够大，对于足够大的所有\(a\)，\(c(\mu(a,b)-\mu(b,a\bmod b))\)将会是\(O((1+\lg q) \lg b)\)的上界。

c

对于EUCLID算法的某个参数迭代序列\(r_1,r_2,r_3,\dots,r_k\)，其中\(r_1=a,r_2=b,r_k=0\)，总共的比特操作次数\(T(a,b)\)的上界为

\(\begin{aligned} T(a,b)&\le \sum_{i=1}^{k-3} c(\mu(r_i,r_{i+1})-\mu(r_{i+1},r_{i+2}))\\ &=c(\mu(a,b)-\mu(r_{k-2},r_{k-1}))\\ &\le c\mu(a,b) \end{aligned}\)

因此\(T(a,b)=O(\mu(a,b))\)。由于\(\lg a=\lg b=O(\beta)\)，因此更一般的情况下，有\(T(a,b)=O(\beta)\)。

31-3

a

因为求解\(F_n\)需要求解\(F_{n-1},F_{n-2}\)。假设求解\(F_n\)所需要花费的时间为\(T(n)\)，那么有

\[T(n)=T(n-1)+T(n-2)+\Theta(1)\]

我们希望证明\(T(n)=\Theta(F_n)\)。

首先证明\(T(n)=O(F_n)\)。假设对于\(k=0,1,\dots,n-1\)，都有\(T(k)\le cF_k-c_1k\)。考虑\(T(n)\)，那么有

\(\begin{aligned} T(n)&=T(n-1)+T(n-2)+\Theta(1)\\ &\le cF_{n-1}-c_1(n-1)+cF_{n-2}-c_1(n-2)+\Theta(1)\\ &= cF_n-c_1n+(\Theta(1)-c_1(n-3))\\ &\le cF_n-c_1n &\qquad(A) \end{aligned}\)

其中步骤\((A)\)假设了当\(n\)足够大时，\(c_1(n-3)\)的增长速度快过\(\Theta(1)\)。

因此有\(T(n)=O(F_n)\)。

接下来证明\(T(n)=\Omega(F_n)\)。假设对于\(k=0,1,\dots,n-1\)，都有\(T(k)\ge cF_k+c_2k\)。考虑\(T(n)\)，那么有

\(\begin{aligned} T(n)&=T(n-1)+T(n-2)+\Theta(1)\\ &\ge cF_{n-1}+c_2(n-1)+cF_{n-2}+c_2(n-2)+\Theta(1)\\ &= cF_n+c_2n+(\Theta(1)+c_2(n-3))\\ &\ge cF_n+c_2n &\qquad(B) \end{aligned}\)

其中步骤\((A)\)假设了当\(n\)足够大时才成立。

因此有\(T(n)=\Theta(F_n)=\Theta(\phi^n)\)，也就是说，\(T(n)\)的运行时间是指数级别的。

b

该题目的做法和题目14.1-6完全一致。

1
2
3
4
5
6
FIB(n)
  let fib[0 : n] be a new array
  fib[0] = fib[1] = 1
  for i = 2 to n
    fib[i] = fib[i - 1] + fib[i - 2]
  return fib[n]

c

\(F_n\)可以写成如下矩阵乘法的形式：

\[ \begin{bmatrix} F_n\\ F_{n+1} \end{bmatrix} = \begin{bmatrix} 0&1\\ 1&1 \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n} \end{bmatrix} \]

那么为了计算\(F_n\)，将上式写成矩阵的幂，有

\[ \begin{bmatrix} F_n\\ F_{n+1} \end{bmatrix} = \begin{bmatrix} 0&1\\ 1&1 \end{bmatrix}^k \begin{bmatrix} F_{0}\\ F_{1} \end{bmatrix} \]

对于一个\(2\times 2\)矩阵自乘的运算，可以使用\(8\)次乘法和\(4\)次加法完成。

假设子程序MUL-MATRIX(A, B)是将两个矩阵相乘的乘法，那么可以写出这个算法的伪代码FIB'，其计算时间复杂度为\(O(\lg n)\)。

1
2
3
4
5
6
7
8
FIB'(n)
  A = [[0], [1]]
  B = [[0, 1], [1, 1]]
  while n > 0
    if n & 1
      A = MUL-MATRIX(B, A)
    B = MUL-MATRIX(B, B)
  return A[0, 0]

d

由于\(\beta\)是\(n\)的位数，因此有\(\beta=\Theta(\lg n)\)。

对于题目31-3-a的算法，它总共执行了\(\Theta(T(n))\)次加法，因此其时间复杂度为\(\Theta(\phi^n\cdot\lg n)\)。

对于题目31-3-b的算法，它总共执行了\(n-1\)次加法，因此其时间复杂度为\((n-1)\Theta(\beta)=\Theta(n\lg n)\)。

对于题目31-3-c的算法，它一共执行了\(\Theta(\lg n)\)次的矩阵操作，并且每次算法最多只包含\(8\)次乘法，\(4\)次加法，因此其时间复杂度为\(\Theta(\lg n)\cdot(8\Theta(\beta^2)+4\Theta(\beta))=\Theta(\lg ^3n)\).

31-4

a

如果\(\mathbb{Z}_p^{\ast}\)中的两个不同数\(x,y\)它们的平方值相同，那么有\(x^2=y^2\pmod p\)，即\((x+y)(x-y)=0\pmod p\)。那么由于\(x\neq y\)，有\(x+y\equiv 0\pmod p\)。因此这两个数在\(\mathbb{Z}_p^{\ast}\)中是互为“相反数”。

也就是说，如果\(x^2=a\pmod p\)，那么同样有\((p-x)^2=a\pmod p\)。\((x,p-x)\)是成对出现的。而\(\mathbb{Z}_p^{\ast}\)中有\(p-1\)个元素，因此\(\mathbb{Z}_p^{\ast}\)中二次剩余为\(\dfrac{p-1}{2}\)个，

b

这个二次剩余的判别法称为欧拉准则。

首先，先证明\(a^{(p-1)/2}\bmod p\)的值要么为\(1\)，要么为\(-1\)。通过费马小定理可以知道，\(a^{p-1}=1\pmod p\)，并且\(p-1\)是个偶数，因此对费马小定理的式子进行化简，可以得到

\[(a^{(p-1)/2}+1)(a^{(p-1)/2}-1)=0\pmod p\]

由于\(p\)是质数，因此\(a^{(p-1)/2}\bmod p\)的值要么为\(1\)，要么为\(-1\)，才能确保上式成立。

令\(g\)是\(\mathbb{Z}_{p}^{\ast}\)中的一个原根，那么\(\mathbb{Z}_{p}^{\ast}\)中所有的元素都可以通过\(g^1,g^2,\dots,g^{p-1}\)来表示出。

如果\(a\)是一个二次剩余，那么\(\exists x\in \mathbb{Z}_{p}^{\ast}\)使得\(x^2=a\pmod p\)成立，此时有\(\left(\dfrac{a}{p}\right)=a^{(p-1)/2}=x^{p-1}=1\pmod p\)。

否则，如果\(a\)不是二次剩余，那么存在整数\(i\)使得\(a=g^{2i+1}\)。那么有\(\left(\dfrac{a}{p}\right)=a^{(p-1)/2}=(g^{2i+1})^{(p-1)/2}=(g^{(p-1)/2})^{2i+1}=(-1)^{2i+1}=-1\pmod p\)。

接下来解释为什么\(g^{(p-1)/2}=-1\pmod p\)。这是因为\(g\)是原根，生成群\(\langle g\rangle\)中的元素各不相同，又因为\(g^{p-1}=1\pmod p\)，所以\(g^{(p-1)/2}=-1\pmod p\)。

判断\(a\)是否为二次剩余的算法由IS-QUADRATIC-RESIDUE给出。它使用了MODULAR-EXPONENTIATION作为子程序来计算\(a^{(p-1)/2}\bmod p\)的值，因此其时间复杂度为\(O(\lg p)\)。

1
2
IS-QUADRATIC-RESIDUE(a, p)
  return MODULAR-EXPONENTIATION(a, (p - 1) / 2, p) == 1

如果不忽略运算操作本身的开销，那么如下考虑：这个子程序进行了\(O(\lg p)\)次迭代，每次迭代中进行了常数次的乘法计算和取模计算，每次计算需要进行\(O(\lg^2p)\)比特的开销。因此这个判断算法的时间复杂度为\(O(\lg^3p)\)。

c

按照勒让德符号的定义，如果\(a\)是模\(p\)下的一个二次剩余，并且\(p=4k+3\)，那么有

\(\left(\dfrac{a}{p}\right)=a^{(p-1)/2}=a^{2k+1}=1\pmod p\)

在这里，只需要验证\(a^{k+1}\)是否为\(a\)的平方根即可，有

\(\begin{aligned} (a^{k+1})^2&=a^{2k+2}\\ &=a\cdot a^{2k+1}\\ &=a&\pmod p \end{aligned}\)

因此\(a^{k+1}\)是\(a\)的平方根。计算这个值只需要调用MODULAR-EXPONENTIATION(a, (p + 1) / 2, p)即可。其运行时间和题目31-4-b分析的相同，为\(O(\lg p)\)。如果考虑运算操作本身的开销，那么为\(O(\lg ^3p)\)。

d

由于非二次剩余恰好在\(\mathbb{Z}_p^{\ast}\)中只占一半，因此我们最简单的方法是在这个集合中均匀地随机选择一个元素，用欧拉准则进行判断它是否是二次剩余即可，如果不是那么就返回这个元素，算法终止；否则就继续下一次抽样。

这个随机选择一个元素次数符合参数为\(\dfrac{1}{2}\)的指数分布，因此这个算法的期望抽取次数为\(2\)。最终这个算法的期望时间复杂度和31-4-b分析的相同，为\(O(\lg p^3)\)