算法导论31.6 Exercises 答案

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