模 m 求幂, 略作补充. 原文要解决的问题是给定 a, n, m 求 $a^n$ 除以 m 所得余数.
解: $a^n = a^{n_0} \cdot a^{2n_1} \cdot a^{4n_2} \cdots a^{2^kn_k}$, 由命题 4.6(2) 可知一旦我们知晓了 $a^{2^in_i}$ 除以 m 所得余数为 $c_i$, 即 $a^{2^in_i} \equiv c_i \mod m$, 则 $a^n \equiv \prod_{i=0}^k c_i \mod m$. 由原文 (ii) 计算出来的余数 $a_i$ 是 $a_{i-1}^2$ 除以 m 所得余数, 这里经过计算可得 $a_i^{n_i} \equiv c_i \mod m$, 即 $a^n \equiv a_0^{n_0}a_1^{n_1} \cdots a_k^{n_k} \mod m$.
同余线性方程组的求解. 关于原文 (iii) 步我实在没有看懂, 我证明不了转换前方程 f
\[\begin{align} x &\equiv b_i \mod m_i \\ x &\equiv b_j \mod m_j \end{align}\]与转换后方程 g
\[\begin{align} x &\equiv b_i \mod \frac{m_i}{m_{ij}} \\ x &\equiv b_i \mod m_{ij} \\ x &\equiv b_j \mod \frac{m_j}{m_{ij}} \end{align}\]具有相同的解集合; 这里可以证明 ${x | x \in f} \subseteq {x | x \in g}$, 但无法证明 ${x | x \in g} \subseteq {x | x \in f}$. 这里我重新梳理下同余线性方程组的求法.
P.S. 我曾经以为这里 $(\frac{m_i}{m_{ij}}, m_{ij}) = 1$, 但并不是, 反例: $(8,4)=4, (8/4,4) = 2$.
- 首先任何形如 $a_i x \equiv b_i \mod m_i$ 的方程组都可以转换为 $x \equiv b_i’ \mod m_i’$ 形式.
解: 令 $d_i = (a_i, m_i)$, 根据命题 4.9 可知仅当 $d_i \mid b_i$ 时才有解. 在解存在的情况下, 可令 $a_i = d_i l_1, m_i = d_i l_2, b_i = d_i l_3$, 这里 $l_1, l_2, l_3$ 均为整数, 且 $(l_1, l_2) = 1$. $a_i x \equiv b_i \mod m_i$ 就等同于 $d_il_1 x \equiv d_i l_3 \mod d_i l_2$, 根据命题 4.8(2) 该式等同于 $l_1 x \equiv l_3 \mod l_2$. 由于 $(l_1, l_2) = 1$, 即 $[l_1] \in (\mathbb{Z}/l_2\mathbb{Z})^{\times}, \exists y, l_1 y \equiv 1 \mod l_2$. 根据 4.6(2) 可知 $l_1 x \equiv l_3 \mod l_2$ 等同于 $l_1 x y\equiv l_3 y \mod l_2; \forall x, l_1 y x \equiv x \mod l_2$, 即可得 $a_i x \equiv b_i \mod m_i$ 等同于 $x \equiv l_3 y \mod l_2$.
P.S. 原文这里第 (ii) “求解后同余方程组归结到 $x \equiv b_i \mod m_i$ 的情形”, 我一度以为这里的 $b_i, m_i$ 就是原线性方程组的 $b_i, m_i$, 搞得我想了半天这里是怎么抹掉 $a_i$ 的…
- 这样我们仅考虑形如 $x \equiv b_i \mod m_i$ 方程组求解, 此时 $m_i$ 两两互素.
解: 首先可知在 $m_i$ 互素情况下, 参考 4.8.zy4 该方程组的求解就等同于寻找 $x$ 使得 $\Phi(x \mod m_1 \cdots m_k) = (b_1 \mod m_1, \cdots, b_k \mod m_k)$, 见 “中国剩余定理满射的证明” 给出了一种求解 $x$ 的方案.
- 接下来我们考虑形如 $x \equiv b_i \mod m_i$ 方程组求解, 此时 $m_i$ 并不两两互素.
首先看个结论, 所有解的集合是 $K=[m_1, \cdots, m_k]$ 的一个同余类; 这算定理 4.22 的扩充吧.
证明: 设 $x_1$ 是满足方程组的一个解, 首先证对于任何满足条件的其他解 $x_2$ 都有 $x_2 \in x_1 \mod K$. 此时 $x_1 \equiv b_i \mod m_i, x_2 \equiv b_i \mod m_i$ 即 $x_1 \equiv x_2 \mod m_i$, 根据 4.8(3) 可得 $x_1 \equiv x_2 \mod K$. 再证 $\forall x_2 \in x_1 \mod K$ 都是方程的解, 易知 $x_2 = x_1 + Kl$, 易证由 $x_1 \equiv b_i \mod m_i$ 可推出 $x_1 + Kl \equiv b_i \mod m_i$.
最后证对于 $\forall x_3, x_3 \not\equiv x_1 \mod K, \forall y \in x_3 \mod K$, y 都不可能是方程组的解; 假设此时 y 是方程组的解, 则根据上文可知 $y \in x_1 \mod K$, 矛盾!
根据这个结论可知我们只要找到方程组的一个解即可. 对于第一个方程, 易知 $x = b_1$ 就是方程的解; 对于第 N 个方程, 令 $M = [m_1, \cdots, m_{N-1}], x_{N-1}$ 为前 N-1 个方程的解; 由上面结论可知 $x_{N-1} \mod M = {x_{N-1} + tM, t\in Z }$ 都是前 N-1 个方程的解. 我们现在要做的是从这么些解中找到一个满足第 N 个方程, 即寻找 $t_0$ 使得 $x_{N-1} + t_0M \equiv b_N \mod m_N$, 即 $t_0M \equiv b_N - x_{N-1} \mod m_N$, 见命题 4.9 可知 $t_0$ 如何求解. 如此一直将 N 迭代到最后一个方程便可得方程的一个解, 继而可得方程的所有解!
素性判定, 原文这里提到:
由费马小定理, n 是素数当且仅当对于所有 $0 \lt a \lt n, a^{n-1} \equiv 1 \mod n$.
首先由费马小定理易证 n 是素数时, $\forall a \in (0, n), a^{n-1} \equiv 1 \mod n$. 这里证明下由 $\forall a \in (0, n), a^{n-1} \equiv 1 \mod n$ 推断出 n 是素数:
证法1, 我们可以通过证明 $\forall a, d=(a, n)=1$ 来证明 n 是素数. 此时由 $d \mid a, d \mid n, n \mid a^{n-1} - 1$ 可知 $d \mid a^{n-1}, d \mid a^{n-1} - 1$, 易证此时 d 只能为 1!
证法2, 假设 n 不是素数, 则 n 可以写作 $n = cd, 1 \lt c, d \lt n$, 此时可证 e =$(c^{n-1}-1, c) = 1, (d^{n-1}-1, d) = 1$, 即由 $e\mid c, e \mid c^{n-1}, e \mid c^{n-1}-1$ 可以推出 e = 1. 可证 $n \nmid c^{n-1}-1$, 假设 $n \mid c^{n-1}-1$ 则可知 $c \mid c^{n-1}-1, (c, c^{n-1}-1) \ge c \gt 1$ 矛盾! 即 $c^{n-1} \not\equiv 1 \mod n$. 矛盾!
RSA 算法, 唉用了这么多年 RSA 今天才知道她背后的原理, 惭愧呀! 这里对原文略作补充.
- 结论1: $\forall m \in [0, n)$ 有 $(m^e)^d \equiv m \mod n$
证明: 根据定理 4.18 可知 $(m^e)^d \equiv m \mod n$ 等价于 $(m^e)^d \equiv m \mod p$ 且 $(m^e)^d \equiv m \mod q$, 这里我们只证 $(m^e)^d \equiv m \mod p$. 当 $m \equiv 0 \mod p, p \mid m$ 时易证此时结论成立. 接下来考虑 $m \not\equiv 0 \mod p$, 即 $m \in \mathbb{F}_p^{\times}, (m, p) = 1$ 时, 此时由费马小定理结合 4.23.zy3 可得 $m^{p-1} \equiv 1 \mod p$.
由 $ed \equiv 1 \mod (p-1)(q-1)$ 可得 $(p-1)(q-1) \mid (ed - 1)$, 即 $ed - 1 = h(p-1), h \in N$. 由 4.6(2) $m^{p-1} \equiv 1 \mod p$ 可得 $(m^{p-1})^h \equiv 1 \mod p$, 结合 $m \equiv m \mod p$ 可得 $(m^{p-1})^hm \equiv m \mod p, (m^{p-1})^hm = m^{ed}$, 结论得证.
- 所以我设想的加密解密流程是: 确定明文 $A, A \in [0, n)$, 计算出密文 $B = A^e$, 发送 B, 接受方收到 B 之后, 进行 $B^d \mod m$ 可得 A. 但原文指出在发送时实际上 $B = A^e \mod n$, 为啥这里要取除以 n 之后得到的余数呢? 会不会出现不同的消息计算取余之后得到相同的 B?
解: 首先看这里 $B = A^e \mod n$ 多了个取余操作之后会不会导致接受方出现问题. 由 $B \equiv A^e \mod n$ 结合 4.6(2) 可知 $B^d \equiv (A^e)^d \mod n$, 即 $B^d \mod n = (A^e)^d \mod n$. 所以可以看到多了个取余操作不会导致接受方出现问题, 至于这里为啥多了个取余操作我理解是减少发送报文长度, 毕竟 $A^e \mod n$ 的位数应该是远小于 $A^e$ 的位数的; 另外这样也可以降低接受方计算复杂度.
至于会不会出现不同的消息计算取余之后得到相同的 B? 由上段内容结合反证法可以看到不会!
