算法导论31 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 5.2k 阅读时长 ≈ 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

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

我们希望证明$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$可以写成如下矩阵乘法的形式：

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

对于一个$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$是个偶数，因此对费马小定理的式子进行化简，可以得到

由于$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)$