算法导论31.6 Exercises 答案

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

31.6-1

$\begin{aligned}
i&& 0 && 1 && 2 && 3 && 4 && 5 && 6 && 7 && 8 && 9 && 10 \
1^i \bmod 11 && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \
2^i \bmod 11 && 1 && 2 && 4 && 8 && 5 && 10 && 9 && 7 && 3 && 6 && 1 \
3^i \bmod 11 && 1 && 3 && 9 && 5 && 4 && 1 && 3 && 9 && 5 && 4 && 1 \
4^i \bmod 11 && 1 && 4 && 5 && 9 && 3 && 1 && 4 && 5 && 9 && 3 && 1 \
5^i \bmod 11 && 1 && 5 && 3 && 4 && 9 && 1 && 5 && 3 && 4 && 9 && 1 \
6^i \bmod 11 && 1 && 6 && 3 && 7 && 9 && 10 && 5 && 8 && 4 && 2 && 1 \
7^i \bmod 11 && 1 && 7 && 5 && 2 && 3 && 10 && 4 && 6 && 9 && 8 && 1 \
8^i \bmod 11 && 1 && 8 && 9 && 6 && 4 && 10 && 3 && 2 && 5 && 7 && 1 \
9^i \bmod 11 && 1 && 9 && 4 && 3 && 5 && 1 && 9 && 4 && 3 && 5 && 1 \
10^i \bmod 11 && 1 && 10 && 1 && 10 && 1 && 10 && 1 && 10 && 1 && 10 && 1 \
\end{aligned}$

因此，$\mathbb{Z}_{11}^{\ast}$中的所有的元素的阶为：

$\begin{aligned}
\text{ord}{11}(1) &= 1 \
\text{ord}{11}(2) &= 10 \
\text{ord}{11}(3) &= 5 \
\text{ord}{11}(4) &= 5 \
\text{ord}{11}(5) &= 5 \
\text{ord}{11}(6) &= 10 \
\text{ord}{11}(7) &= 10 \
\text{ord}{11}(8) &= 10 \
\text{ord}{11}(9) &= 5 \
\text{ord}{11}(10) &= 2 \
\end{aligned}$

因此，$\mathbb{Z}_{11}^{\ast}$中的最小原根为$g=2$。并且有此表：

$\begin{aligned}
\text{ind}{11,2}(1) &= 0 \
\text{ind}{11,2}(2) &= 1 \
\text{ind}{11,2}(3) &= 8 \
\text{ind}{11,2}(4) &= 2 \
\text{ind}{11,2}(5) &= 4 \
\text{ind}{11,2}(6) &= 9 \
\text{ind}{11,2}(7) &= 7 \
\text{ind}{11,2}(8) &= 3 \
\text{ind}{11,2}(9) &= 6 \
\text{ind}{11,2}(10) &= 5 \
\end{aligned}$

31.6-2

$x^2\equiv 1\pmod {p^e}$意味着$x^2-1\equiv 0\pmod {p^e}$。由于$x^2-1=(x+1)(x-1)$，因此$p^2\mid (x+1)(x-1)$。

31.6-3

1
2
3
4
5
6
7
MODULAR-EXPONENTIATION(a, b, n)
  if b == 0
    return 1
  while b mod 2 == 0
    a = a * a mod n
    b = b / 2
  return a * MODULAR-EXPONENTIATION(a * a mod n, (b - 1) / 2, n) mod n

31.6-4

1
2
3
4
5
6
7
8
9
MODULAR-EXPONENTIATION(a, b, n)
  d = 1
  while b > 0
    if b mod 2 == 1
      d = d * a mod n
      b = b - 1
    a = a * a mod n
    b = b / 2
  return d

31.6-5

根据欧拉定理，有$a^{\phi(n)}\equiv 1 \pmod n$。那么两边同时乘上$a^{-1}$，得到$a^{-1}\equiv a^{\phi(n)-1}\pmod n$。

那么，仅需要调用MODULAR-EXPONENTIATION(a, phi - 1, n)即可计算出$a^{-1}$。