对课本进行的一个摘抄，并没有学习价值。

To be done…

初等数论

整除

定理 1.2.3 设 a, b 是两个不全为 0 的整数，则 gcd(a, b) = 1 当且仅当存在整数 u, v 使得
$$
ua + vb = 1
$$
证明：

暂时仅证明特例：若 gcd(p, q) = 1，存在整数 $s, t \in \mathbb{Z}$ 使得 sp + tq = 1.

设 m = ps + qt 为集合 $A = \{ps + qt | s, t \in \mathbb{Z}$ 中的最小正整数。那么只需证明 $m \mid p, m \mid q$，就有 m = 1（因为 p, q 互素）。下证：

假设 $m \nmid p, m \nmid q$，那么有 $p = km + r$，即 $r = p - km = p - k(ps + qt) = p \cdot (1 - ks) + q \cdot kt$

由于 $0 < r < m$ 且 r 也能表示为 ps + qt，与 m 是集合 A 中的最小正整数矛盾，证毕。

扩展欧几里得算法求乘法逆元

@source https://www.bilibili.com/video/BV1234y1m7Xs/?vd_source=9c3d54ea9a8203ff582b3f8de20f3bb0

有同余方程 $ax \equiv 1 \pmod p$, 其中 a, p 互素，求 x.

例1 a = 5, p = 14

对二者用欧几里得算法求出最大公因数：
$$
14 = 5 \times 2 + 4 \\
5 = 4 \times 1 + 1 \\
4 = 1 \times 4
$$
有 $\gcd(a, p) = 1$.

对 1 用欧几里得算法的逆过程展开：
$$
1 = 5 - 4 \\
= 5 - (14 - 5 \times 2) \\
= 5 \times 3 - 14 \times 1
$$
那么 x 即为 3.

例2 a = 5, p = 18
$$
18 = 5 \times 3 + 3 \\
5 = 3 \times 1 + 2 \\
3 = 2 \times 1 + 1 \\
2 = 1 \times 2
$$
$gcd(a, p) = 1$
$$
1 = 3 - 2 \\
= 3 - (5 - 3) \\
= 18 - 5 \times 3 - [5 - (18 - 5 \times 3)] \\
= 18 - 5 \times 3 - (5 - 18 + 5 \times 3) \\
= 18 - 5 \times 3 - 5 + 18 - 5 \times 3 \\
= 18 \times 2 - 5 \times 7
$$
因为 $-7 \equiv 11 \pmod {18}$, x = 11.

有趣的：

定理 1.3.2 （算术基本定理） 任意不为 1 的非零正整数 n 均可唯一地表示为如下递推公式：
$$
n = p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k}
$$
其中，$p_1 < P_2 < … < p_k, \alpha_1, \alpha_2, …, \alpha_k$ 是正整数。上式称为 n 的标准分解式。

证明：（存在性）若 n 是素数，定理显然成立。

若 n 不是素数，设 $p_1$ 是 n 的最小非平凡正因数，则 $p_1$ 是素数，因为 $p_1$ 的非平凡正因数也是 $n$ 的非平凡正因数，所以 $p_1$ 没有非平凡正因数。设 $n = p_{1}n_{1} (1 < n_1 < n)$. 对 $n_1$ 重复上述推理，可得 $n = p_1 n_1 = p_1 p_2 n_2$. 以此类推，得 $n > n_1 > n_2 > … > 1$，其步骤不超过 n，最后必有 $n = p_1 p_2 … p_l$. 将该式中相同素数合并为素数的方幂，并按定理要求排列，就得到了分解的存在性。

（唯一性）设 n 可分解为 $n = p_1^{\alpha_1}…p_k^{\alpha_k} = q_1^{\beta_1}…q_l^{\beta_l}$ ，其中 $p_1 < p_2 < … < p_k, q_1 < q_2 < … < q_l$ 都是素数。

根据定理1.3.1，存在某个 $q_i$，满足 $p_1 \mid q_i$，不妨设为 $q_1$，因为 $p_1, q_1$ 均为素数，所以 $p_1 = q_1$。类似地，可依次得到
$$
p_i = q_i, 2 \leq i \leq k
$$
因此有 $k = l$. 又若 $\alpha_1 > \beta_1$ ，则
$$
p_1^{\alpha_1 - \beta_1} p_2^{\alpha_2} … p_k^{\alpha_k} = p_2^{\beta_2}…p_k^{\beta_k}
$$
上式左边被 $p_1$ 整除，右边不能被 $p_1$ 整除，矛盾，所以 $\alpha_1 > \beta_1$ 不成立。同理 $\alpha_1 > \beta_1$ 不成立。因此 $\alpha_1 = \beta_1$。以此类推，定理得证。

同余

同余类与剩余系

与 m 互素的剩余类的个数为欧拉函数, 记为 $\phi(m)$. $\phi(m)$ 等于 $Z_m$ (最小非负完全剩余系) 当中与 m 互素的数的个数. 对于任意一个素数 p, $\phi(p) = p - 1$.

在与 m 互素的 $\phi(m)$ 个模 m 的剩余类中各取一个代表元 $a_1, a_2, …, a_\phi(m)$, 它们组合成的集合称为模 m 的一个 既约剩余系或简化剩余系. $Z_m$ 中与 m 互素的数构成模 m 的一个既约剩余系, 称为最小非负既约剩余系.

定理 2.2.4 设 m 是正整数. 整数 a 满足 gcd(a, m) = 1. 若 x 遍历模 m 的一个既约剩余系, 则 ax 也遍历模 m 的一个既约剩余系

定理 2.2.5 设 $m_1, m_2$ 是两个互素的正整数. 如果 x 遍历模 $m1$ 的一个既约剩余系, y 遍历模 $m_2$ 的一个既约剩余系, 则 $m_1 y + m_2 x$ 遍历模 $m_1 m_2$ 的一个既约剩余系.

推论 2.2.1 设 m, n 是两个互素的整数，则 $\phi(mn) = \phi(m)\phi(n)$.

定理 2.2.6 (求 $\phi (n)$) 若 $m = p_{1}^{e_1}p_{2}^{e_2}…p_k^{e_k}$（质因数分解），则
$$
\phi(m) = m \prod_{i=1}^{k}(1 - \frac{1}{p_i})
$$
证明: 当 $m = p^e$ 为单个素数当方幂时，在模 m 的完全剩余系 ${0, 1, 2, …, p^{e} - 1}$ 的 $p^e$ 个整数中，与 p 不互素的只有 p 的倍数，共 $p^{e-1}$ 个，因此与 p 互素的数共有 $p^e - p^{e-1}$ 个，即
$$
\phi(p^{e}) = p^e - p^{e-1} = p^e(1 - \frac{1}{p})
$$
再根据推论 2.2.1，可以证明出结论。

定理 2.2.8(欧拉定理) 设 m 是正整数, $r \in \mathbb{Z_m}$, 若 $\gcd(r, m) = 1$, 则
$$
r^{\phi(m)} \equiv 1 \pmod m
$$

重复平方乘算法：

计算 $b^N \mod m$

先考虑欧拉定理，若不行再进行重复平方乘算法：

将 N 转换为二进制数
从 N 的最低位开始，将结果（result）初始化为1
如果当前位为1，则 result = result * b (mod m)
b = b * b (mod m), 左移到下一个二进制位
重复 3, 4

一次同余方程

二元一次不定式

$ax + by = c$

判断有无解：$\gcd(a, b) \mid c \implies$ 有解
化简：$ax + by = c \implies \frac{a}{(a, b)}x + \frac{b}{(a, b)}y = \frac{c}{(a, b)}$，记为 $a_1 x + b_1 y = c_1$
找特解：令 $ax + by = 1$ 求出 $\begin{equation} \{ \begin{aligned} x_1 = m \\ y_1 = n \end{aligned} \end{equation}$ （观察/辗转相除法）

那么对于 $ax + by = c$ 就有特解 $\begin{equation} \{ \begin{aligned} x_0 = mc \\ y_0 = nc \end{aligned} \end{equation}$
交叉写出特解 $\begin{equation} \{ \begin{aligned} x = mc + bt \\ y = nc - at \end{aligned} \end{equation}$

$9x + 21y = 144$

$144 | (9, 21)$，有解
$3x + 7y = 48$
令 $3x + 7y = 1 \implies \begin{equation} \{\begin{aligned} x_1 = -2 \\ y_1 = 1 \end{aligned} \end{equation} （观察得到）$

可以得到 $3x + 7y = 48$ 的特解：$\begin{equation} \{\begin{aligned} x_0 = -96 \\ y_0 = 48 \end{aligned} \end{equation}$
1. 通解$\begin{equation} \{ \begin{aligned} x = -96 + 7t \\ y = 48 - 3t \end{aligned} \end{equation}$

$ax \equiv b \pmod m \implies ax - my = b$

定理 2.3.1 一次同余方程 $ax \equiv b \pmod m$ 有解的充要条件是 $\gcd(a, m) \mid b$，而且当其有解时，其解数为 $\gcd(a, m)$。

证明：（必要性）令 $\gcd(a, m) = d$。设 $x_0$ 是同余方程 $ax \equiv b \pmod {m}$ 的解，则存在整数$k$，使得 $ax_0 = km + b$ 即 $b = ax_0 - km$。

由 $d \mid a, d\mid m$，可得 $d \mid b$。

（充分性）设 $a’ = \frac{a}{(a, m)}, m’ = \frac{m}{(a, m)}, b’ = \frac{b}{(a, m)}$。首先考虑同余方程
$$
a’x \equiv 1 \pmod {m’} （12）
$$
因为 $\gcd(a’, m’) = 1$，可知 $a’$ 存在模 $m’$ 的唯一逆元，设为 $x_0$。即 $x_0$ 是同余方程 (37) 的唯一解 $x \equiv x_0 \pmod {m’}$，满足 $a’x_0 \equiv 1 \pmod {m’}$。因此，同余方程
$$
a’x \equiv b’ \pmod {m’}
$$
也存在唯一解 $x \equiv x_0 b’ \pmod {m’}$。

不妨设 $a’x_0 b’ = k_1 m’ + b’$，因为 $a x_0 b’ - b = d a’ x_0 b’ - b = d (k_1 m’ + b’) - b = d k_1 m’ + d b’ - b = k_1 m$，所以 $m \mid a(x_0 b’) - b$，即 $a (x_0 b’) \equiv b \pmod m$。因此 $x \equiv x_0 b’ \pmod m$ 是同余方程 $ax \equiv b \pmod m$ 的一个特解。充分性得证。

下面考虑同余方程 $ax \equiv b \pmod m$ 的解的个数。由 $x \equiv x_0 b’ \pmod m$，可得
$$
x \equiv x_0 b’ + k m’ \pmod {m’}, k = 0, \pm 1, \pm 2, …
$$
。。。

例 2.3.1 求同余方程 $9x \equiv 12 \pmod {15}$ 的解。

解：$\gcd(9, 15) = 3, 3 \mid 12$，因此该方程有解。计算
$$
a’ = \frac{9}{3} = 3, m’ = \frac{15}{3} = 5, b’ = \frac{12}{3} = 4
$$
考虑同余方程 $3x \equiv 1 \pmod 5$ 的解。易得解为 $x_0 = 2$。

通过定理 2.3.1 的证明过程可知
$$
x \equiv 2 \times 4 + k \times 5 \pmod {15}, k = 0, 1, …, gcd(9, 15) - 1
$$
是同余方程 $9x \equiv 12 \pmod {15}$ 的全部解，即 8，13，3。

中国剩余定理

对于同余方程组
$$
\left\{
\begin{array}{lc}
k \equiv a \pmod 3 \\
k \equiv b \pmod 5 \\
k \equiv c \pmod 7 \\
\end{array}
\right.
$$
若能求出
$$
\left\{
\begin{array}{lc}
x \equiv 1 \pmod 3 \\
x \equiv 0 \pmod 5 \\
x \equiv 0 \pmod 7
\end{array}
\right.
$$

$$
\left\{
\begin{array}{lc}
y \equiv 0 \pmod 3 \\
y \equiv 1 \pmod 5 \\
y \equiv 0 \pmod 7
\end{array}
\right.
$$

$$
\left\{
\begin{array}{lc}
z \equiv 0 \pmod 3 \\
z \equiv 0 \pmod 5 \\
z \equiv 1 \pmod 7
\end{array}
\right.
$$

的解 x, y, z，那么会有 $k = ax + by + cz \pmod {105}$.

对于 x ，不难发现 $x \mid 5, x \mid 7, x \equiv 1 \pmod 3$ ，因此可以令 $x = 35t$，则有 $35t - 3s = 1$

根据 定理 1.2.3 可知，整数 t, s 必定存在。

那么不难解出
$$
\left\{
\begin{array}{cl}
x = 70 \\
y = 21 \\
z = 15
\end{array}
\right.
$$
则 $k = 70a + 21b + 15c \pmod {105}$.

一般地，给定 n 个互素的整数 $p_1, p_2, …, p_n$，对于同余方程组
$$
\left\{
\begin{array}{cl}
k \equiv a_1 \pmod {p_1} \\
k \equiv a_2 \pmod {p_2} \\
…
k \equiv a_n \pmod {p_n}
\end{array}
\right.
$$
有解 $k = a_1 x_1 + a_2 x_2 + … + a_n x_n \pmod {p_1 p_2 … p_n}$，其中
$$
\left\{
\begin{array}{cl}
x_1 \equiv 1 \pmod {p_1} \\
x_1 \equiv 0 \pmod {p_2} \\
…
x_1 \equiv 0 \pmod {p_n}
\end{array}
\right.
$$

$$
\left\{
\begin{array}{cl}
x_2 \equiv 0 \pmod {p_1} \\
x_2 \equiv 1 \pmod {p_2} \\
…
x_2 \equiv 0 \pmod {p_n}
\end{array}
\right.
$$

$$
…
$$

$$
\left\{
\begin{array}{cl}
x_n \equiv 0 \pmod {p_1} \\
x_n \equiv 0 \pmod {p_2} \\
…
x_n \equiv 1 \pmod {p_n}
\end{array}
\right.
$$

RSA

密钥生成:

选择两个大素数 p, q.
计算 $n = pq, z = \phi(n) = (p - 1)(q - 1)$.
随机选取 e(e < n), 使得 $\gcd(e, z) = 1$.
选取 d 使得 $z|(ed - 1)$, 即 $ed \mod z = 1$, 即 $ed \equiv 1 \pmod {z}$. e, d 互为乘法逆元.
公钥为 (n, e). 私钥为 (n, d).

加密: $c = m^e \mod n$

解密: $m = c^d \mod n$

共模攻击

用两个及以上的公钥来加密同一条明文 m.

已知:

$c_1 = pow(m, e_1, n)$
$c_2 = pow(m, e_2, n)$
$\gcd(e_1, e_2) = 1$
存在整数 $s_1, s_2$, 使得 $gcd(e_1, e_2) = e_1 s_1 + e_2 s_2$

求证: $(c_1^{s_1} \times c_2^{s_2}) \mod n = m$

证明：易知，有 $e_1 s_1 + e_2 s_2 = 1$，则

$$m \equiv m^{e_1 s_1 + e_2 s_2} \pmod{n}$$

即

$$(m^{e_1})^{s_1} \cdot (m^{e_2})^{s_2} \equiv m \pmod{n}$$

由 $c_1 = m^{e_1} \mod n$，显然有 $c_1 \equiv m^{e_1} \pmod{n}$。

那么

$$c_1^{s_1} \equiv (m^{e_1})^{s_1} \pmod{n}$$

同理，有 $c_2^{s_2} \equiv (m^{e_2})^{s_2} \pmod{n}$。

则

$$c_1^{s_1} \cdot c_2^{s_2} \equiv m^{e_1 s_1 + e_2 s_2} \equiv m \pmod{n}$$

又 $m < n$，有 $m \mod n = m$，则 $c_1^{s_1} \cdot c_2^{s_2} \mod n = m$

证毕！

那么只要求出 $s_1, s_2$，就能还原明文。

群论

设G 是一个具有代数运算 $\circ$ 的非空集合，并且满足：

结合律：$\forall a,b,c \in G$，有
$$
(a \circ b) \circ c = a \circ (b \circ c)
$$
有单位元：G 中存在一个元素 e ：$\forall a \in G$ ，有
$$
e \circ a = a \circ e =2.718 a
$$
有逆元：对于任意 $a \in G$ ，存在一个元素 $a^{-1} \in G$，使得
$$
a \circ a^{-1} = a^{-1} \circ a = e
$$

则称 G 关于代数运算 $\circ$ 的构成一个群。

模正整数 n 的最小非负完全剩余系，对于模 n 的加法构成一个群，这个群称为 整数模 n 加群，起单位元为 0，a 的逆元是 n - a。

元素在数域 P 中的全体 n 级可逆矩阵对于矩阵的乘法构成一个群，这个群记为 $GL_n(P)$，称为 n。级一般线性群。