密码学数学基础 - 二次剩余
在前两章中，我们已经掌握了整数关系和同余关系的基本概念，这些工具为我们理解数字之间的关系奠定了基础。而在本章中，我们将进入一个更深层次的领域：二次剩余。
本章存在大量定理和证明，虽然有些定理的证明可能比较复杂，但我们会尽量用通俗易懂的语言来解释这些概念。😎
剩余类与欧拉函数 🧐
剩余类是指在模运算下具有相同余数的整数集合，我们用$Z_n$表示这个集合。
对于一个模数 $n$，剩余类可以表示为 ${[0], [1], [2], \ldots, [n-1]}$，每个整数都属于其中一个剩余类。
定义$Z^*_n = {a \in Z_n | \gcd(a,n) = 1}$，即在模 $n$ 下与 $n$ 互质的剩余类集合。
欧拉函数 $\phi(n)$ 是指在模 $n$ 下与 $n$ 互质的整数的数量，即$Z^*_n$的元素个数。
对于一个正整数 $n$，如果 $n$ 的质因数分解为 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} = n_1 n_2 \cdots n_m$，其中 $p_i$ 是 $n$ 的不同质因数，$k_i$ 是对应的正整数（实际上这里对应算数基本定理，但是这证明比较复杂且没必要，所以略😝）
欧拉函数 $\phi(n)$ 有三个性质：
$ \phi(n) = \prod_{i=1}^{m} \phi(n_i) $
$ \phi(p^k) = p^{k-1}(p-1) $
$ \phi(p) = p - 1 $
那么欧拉函数可以通过以下公式①计算：
欧拉定理与费马小定理 😜
乘法阶是指在模 $n$ 下，一个整数 $a \in Z^*_n$ 的最小的正整数 $k$，使得 $a^k \equiv 1 \mod n$ ,那么在模 $n$ 下，${a^0, a^1, a^2, \ldots\, a^{k-1}}$ 是一个循环序列且每个元素都不相同，直到 $a^k \equiv 1 \mod n$ 时才会回到起点。
所以，对于 $i$, $j$, 如果 $i \equiv j \mod k$，则 $a^i \equiv a^j \mod n$。反之，如果 $a^i \equiv a^j \mod n$，则 $i \equiv j \mod k$。
欧拉定理②是设 $a \in Z^*_n$，则 且 $k \mid \phi(n)$, 其中 $k$ 是 $a$ 的乘法阶。
小费马定理和欧拉定理的关系强相关，当 $n$ 是质数 $p$ 时，$Z^*_p$ 中的每个元素都是与 $p$ 互质的，因此 $\phi(p) = p - 1$。
所以欧拉定理在 $n$ 是质数时就变成了小费马定理，即对于任何整数 $a$，如果 $p \nmid a$，则
二次剩余与勒让德符号 😵💫
二次剩余是指在模 $p$ 下，存在一个整数 $x$ 使得 $x^2 \equiv a \mod p$，则称 $a$ 是模 $p$ 的二次剩余。否则，称 $a$ 是模 $p$ 的二次非剩余。
如何判断一个数是否是模 $p$ 的二次剩余呢？如果恰好是完全平方数，那么它就是二次剩余。比如，$2^2 \equiv 4 \mod 7$。但是不是所有都恰好是完全平方数，但这并不代表这不是二次剩余，比如，$3^2 \equiv 2 \mod 7$，所以 $2$ 是模 $7$ 的二次剩余。所以有时候我们需要更一般的方法来判断一个数是否是二次剩余。
欧拉准则提供了一个判断二次剩余的工具：设 $p$ 是一个奇素数，$a$ 是一个整数，如果 $p \nmid a$，则
注：欧拉准则的证明比较麻烦（尤其是-1的证明），这里不展开讲解了，不要试图挑战数学百年的积累😝
为了更方便地表示一个数是否是模 $p$ 的二次剩余，我们引入了勒让德符号（Legendre symbol）。对于一个整数 $a$ 和一个奇素数 $p$，勒让德符号定义如下：
其本质就可以理解为 $a^{\frac{p-1}{2}}$，勒让德符号具有以下性质：
- $\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right)$
- $\left( \frac{a^2}{p} \right) = 1$，对于任何整数 $a$。
- $\left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}$，这意味着当 $p \equiv 1 \mod 4$ 时，$-1$ 是模 $p$ 的二次剩余；当 $p \equiv 3 \mod 4$ 时，$-1$ 是模 $p$ 的二次非剩余。
- 二次互反律：对于两个奇素数 $p$ 和 $q$，有 $\left( \frac{p}{q} \right) = (-1)^{\frac{(p-1)}{2} \cdot \frac{(q-1)}{2}} \left( \frac{q}{p} \right)$
（二次互反律的证明比较复杂，这里不展开讲解了，学会与自己和解😏）
我们发现 $-1$ 的二次剩余性与 $p$ 的模 $4$ 的结果有关，这也是一个非常有趣的现象。
判断 $-1$ 是否是模 $p$ 的二次剩余，可以通过计算 $p \mod 4$ 来确定：
- 如果 $p \equiv 1 \mod 4$，则 $-1$ 是模 $p$ 的二次剩余。
- 如果 $p \equiv 3 \mod 4$，则 $-1$ 是模 $p$ 的二次非剩余。
由此，当 $p$ 是形如 $4k+1$ 的素数时，我们有简单的方法构造平方根
设 $p \equiv 1 \mod 4$，$ b^2 \equiv -1 \mod p$，$ c$是一个二次非剩余，则
所以 $b \equiv c^{\frac{p-1}{4}} \mod p$ 就是 $-1$ 的一个平方根，另一个为 $-b \mod p$。
如何求解一个数 $a$ 的平方根呢？
如果 $p \equiv 3 \mod 4$，则 $a^{\frac{p+1}{4}}$ 就是 $a$ 的一个平方根③。
如果 $p \equiv 1 \mod 4$，则可以使用 Tonelli-Shanks 算法来求解 $a$ 的平方根，这个算法比较复杂而且含有后续配套，这里先不展开讲解了。
最后，补充一个费马平方和定理：一个素数 $p$ 可以表示为两个整数的平方和（即 $p = x^2 + y^2$）当且仅当 $p \equiv 1 \mod 4$。
关于这个定理的证明，费马当年没能证明，后来欧拉花了几年才一点点完成，放过自己吧。👻
结论①②③证明 😡
结论①证明 😭
我们看 $p^k$ 的情况，设 $p$ 是一个奇素数，$k \geq 1$，则集合共有 $p^k$ 个元素。
其中与 $p^k$ 不互质的元素有 ${0, p, 2p, \ldots, (p^{k-1} - 1)p}$，共 $p^{k-1}$ 个。
因此，与 $p^k$ 互质的元素数量为：$p^k - p^{k-1} = p^{k-1}(p - 1)$。
则 $\phi(p^k) = p^{k-1}(p - 1)$。
设 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$，其中 $p_i$ 是 $n$ 的不同质因数，$k_i$ 是对应的正整数。
根据欧拉函数的定义，我们有：
即欧拉函数等于在模 $n$ 下与 $n$ 互质的整数的数量。
由于 $n$ 的质因数分解，我们可以将 $Z_n$ 分解
根据中国剩余定理，$Z_n$ 中与 $n$ 互质的元素数量等于 $n$ 分解的 $p_i^{k_i}$ 在其对应的子集合中的与 $p_i^{k_i}$ 互质的元素数量的乘积。
因此，我们有：
结论②证明 🥱
二次剩余集合中的整数彼此不同，每个整数乘以 $a$ 后得到的结果也彼此不同而且仍在集合中。所以，乘以 $a$ 后所得的集合不变。
例如，设 $n = 10$，则二次剩余集合为 ${1, 3, 7, 9}$，如果我们选择 $a = 3$，则乘以 $a$ 后的集合为 ${3, 9, 1, 7}$，这与原来的集合是相同的。
现在我们把 $Z^*_n$ 中的整数乘起来，再把乘以 $a$ 后的整数也乘起来，得到：
因为 $Z^*_n$ 中有 $\phi(n)$ 个元素，所以我们可以把 $a$ 提出来，得到：
由于在模 $n$ 下是可逆的，我们可以化简得到：
结论③证明 🥶
设 $p \equiv 3 \mod 4$，则 $p = 4k + 3$，其中 $k$ 是一个非负整数， $a$ 是模 $p$ 下的二次剩余。
根据费马小定理，我们有：
因为 $p \equiv 3 \mod 4$，所以 $p-1 = 4k + 2$，因此：
将上式两边同时乘以 $a$，得到：
注意到 $\frac{p+1}{4} = \frac{4k + 3 + 1}{4} = k + 1$，所以
由欧拉准则，$a^{2k + 1} \equiv 1 \mod p$，所以 $a^{2k + 2} \equiv a \mod p$。因此，$a^{\frac{p+1}{4}}$ 是 $a$ 的一个平方根。
上一章：密码学数学基础 - 同余关系与模运算 👈
下一章：密码学数学基础 - 扩展二次剩余 👈
回到开始：关于我 👈
