二次互反定律

0. 引言：高斯的“黄金定理”

在数论的璀璨星河中，有一颗极为耀眼的明珠——二次互反定律（Law of Quadratic Reciprocity）。伟大的数学家高斯（Carl Friedrich Gauss）极其偏爱这个定理，将其称之为“黄金定理”（Aureum Theorema），并在其一生中给出了多达8种不同的证明方法。

对于计算机科学（尤其是密码学和信息安全）领域的同学来说，二次互反定律不仅仅是一个优美的数学定理，它更是许多现代密码算法（如Rabin密码体制、零知识证明等）的基石。

---

1. 前置知识：什么是“二次剩余”？

要理解二次互反定律，我们首先要知道什么是二次剩余（Quadratic Residue）。

在普通的实数域中，我们知道正数可以开平方，负数不能开平方（在实数范围内）。在**模算术（同余）**的世界里，也有类似的概念。

定义：
设 $p$ 是一个奇素数（即大于2的素数），$a$ 是一个整数且不能被 $p$ 整除（即 $\gcd (a,p)=1$）。
如果存在一个整数 $x$，使得：
$$x^2\equiv a(\mathrm{mod}p)$$
那么我们就称 $a$ 是模 $p$ 的二次剩余（通俗地说，就是 $a$ 在模 $p$ 的意义下可以开平方）。
反之，如果不存在这样的 $x$，我们就称 $a$ 是模 $p$ 的二次非剩余。

举个栗子：

我们取奇素数 $p=7$。我们来看看模 7 的所有非零元素的平方：

• $1^2=1\equiv 1(\mathrm{mod}7)$
• $2^2=4\equiv 4(\mathrm{mod}7)$
• $3^2=9\equiv 2(\mathrm{mod}7)$
• $4^2=16\equiv 2(\mathrm{mod}7)$
• $5^2=25\equiv 4(\mathrm{mod}7)$
• $6^2=36\equiv 1(\mathrm{mod}7)$

观察等号右边的结果，只有 1, 2, 4。
因此：

• 1, 2, 4 是模 7 的二次剩余。
• 3, 5, 6 是模 7 的二次非剩余（因为你找不到任何一个数的平方模 7 等于 3, 5, 6）。

---

2. 核心工具：勒让德符号 (Legendre Symbol)

每次都写“某某是模某某的二次剩余”太麻烦了，数学家勒让德发明了一个非常简洁的符号来记录这件事，记作 $\left(\frac{a}{p}\right)$。

定义：
设 $p$ 是奇素数，$a$ 是任意整数。勒让德符号 $\left(\frac{a}{p}\right)$ 的取值规定如下：

• $\left(\frac{a}{p}\right)=1$：如果 $a$ 是模 $p$ 的二次剩余。
• $\left(\frac{a}{p}\right)=-1$：如果 $a$ 是模 $p$ 的二次非剩余。
• $\left(\frac{a}{p}\right)=0$：如果 $a$ 是 $p$ 的倍数（即 $a\equiv 0(\mathrm{mod}p)$）。

结合上面的例子，我们可以直接写出：
$\left(\frac{2}{7}\right)=1$， $\left(\frac{3}{7}\right)=-1$。

勒让德符号的优美性质：

它完全保留了乘法的性质（完全积性）：
$$\left(\frac{a\cdot b}{p}\right)=\left(\frac{a}{p}\right)\cdot \left(\frac{b}{p}\right)$$
这意味着：

• 两个二次剩余相乘 = 二次剩余 ($1\times 1=1$)
• 两个非剩余相乘 = 二次剩余 ($-1\times -1=1$)
• 一剩余一非剩余相乘 = 二次非剩余 ($1\times -1=-1$)

---

3. 计算捷径：欧拉判别法 (Euler’s Criterion)

虽然勒让德符号很好用，但如果数字很大（比如 $p=10007$），我们总不能把 1 到 $p-1$ 的平方全算一遍吧？这时候轮到欧拉判别法出场了。

欧拉判别法：
对于奇素数 $p$ 和整数 $a$，有：
$$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$$

为什么这个重要？
因为在计算机中，计算 $a^{\frac{p-1}{2}}(\mathrm{mod}p)$ 可以使用快速幂算法，在 $O(\log p)$ 的时间复杂度内光速算出来！这让计算机判断二次剩余变得极其高效。

---

4. 主角登场：二次互反定律

现在，我们要回答一个更深层次的问题：
如果我知道 $p$ 是模 $q$ 的二次剩余（即 $\left(\frac{p}{q}\right)=1$），那么反过来，$q$ 是不是模 $p$ 的二次剩余呢（即 $\left(\frac{q}{p}\right)$ 等于多少）？

这两者之间似乎没有任何直观的联系。但高斯证明了，它们之间有着极其惊人的对称性！这就是二次互反定律。

二次互反定律：
设 $p$ 和 $q$ 是两个不同的奇素数，则：
$$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$$

仔细观察指数部分 $\frac{p-1}{2}\cdot \frac{q-1}{2}$。一个奇数除以4的余数只有两种可能：1 或 3。

• 情况 A： 如果 $p$ 和 $q$ 中至少有一个模 4 余 1（例如 5, 13, 17…）。
  此时 $\frac{p-1}{2}$ 或 $\frac{q-1}{2}$ 中至少有一个是偶数。偶数乘任何数都是偶数。因此 $(-1{)}^{\text{偶数}}=1$。
  结论：$\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$。（它们“互帮互助”，同为剩余或同为非剩余）

• 情况 B： 如果 $p$ 和 $q$ 都模 4 余 3（例如 3, 7, 11…）。
  此时 $\frac{p-1}{2}$ 和 $\frac{q-1}{2}$ 都是奇数。奇数乘奇数还是奇数。因此 $(-1{)}^{\text{奇数}}=-1$。
  结论：$\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)$。（它们“反目成仇”，符号必定相反）

一句话总结二次互反定律：

两个奇素数 $p$ 和 $q$，如果它们都是 $4k+3$ 的形式，那么它们对彼此的二次剩余性质相反；在其他所有情况下，它们对彼此的二次剩余性质相同。

---

5. 不能遗漏的：两个补充定律

二次互反定律解决的是两个奇素数之间的问题。但如果是 $-1$ 或 $2$ 呢？（$-1$ 不是素数，$2$ 不是奇数，无法直接代入上面的定律）。

因此，我们需要两个补充定律：

第一补充定律（针对 $a=-1$）：
$$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}$$
直白翻译：如果 $p\equiv 1(\mathrm{mod}4)$，则 -1 是模 $p$ 的二次剩余；如果 $p\equiv 3(\mathrm{mod}4)$，则 -1 不是。

第二补充定律（针对 $a=2$）：
$$\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}$$
直白翻译：如果 $p\equiv 1$ 或 $7(\mathrm{mod}8)$，则 2 是二次剩余；如果 $p\equiv 3$ 或 $5(\mathrm{mod}8)$，则 2 不是。

---

6. 实战演练

理论学完了，我们来做一道实战题：请问 29 是不是模 43 的二次剩余？
即，求 $\left(\frac{29}{43}\right)$ 的值。

如果是暴力破解，我们要算 1 到 42 的平方，极其繁琐。现在我们用二次互反定律，像变魔术一样降维打击：

Step 1：检查模 4 的余数
$29\equiv 1(\mathrm{mod}4)$。
根据定律，既然有一个模4余1，那么它们“关系好”，直接翻转：
$$\left(\frac{29}{43}\right)=\left(\frac{43}{29}\right)$$

Step 2：利用同余缩小数字
43 模 29 的余数是 14，所以：
$$\left(\frac{43}{29}\right)=\left(\frac{14}{29}\right)$$

Step 3：利用勒让德符号的乘法性质进行质因数分解
$14=2\times 7$，所以：
$$\left(\frac{14}{29}\right)=\left(\frac{2}{29}\right)\times \left(\frac{7}{29}\right)$$

Step 4：分而治之

• 先算 $\left(\frac{2}{29}\right)$：使用第二补充定律。$29\equiv 5(\mathrm{mod}8)$，所以 $\left(\frac{2}{29}\right)=-1$。
• 再算 $\left(\frac{7}{29}\right)$：使用二次互反定律。因为 $29\equiv 1(\mathrm{mod}4)$，再次直接翻转：
  $\left(\frac{7}{29}\right)=\left(\frac{29}{7}\right)$
  缩小数字：$29(\mathrm{mod}7)=1$，所以等于 $\left(\frac{1}{7}\right)$。
  显然 $1^2\equiv 1(\mathrm{mod}7)$，所以 $\left(\frac{1}{7}\right)=1$。

Step 5：得出结论
$$\left(\frac{29}{43}\right)=-1\times 1=-1$$

结论：29 不是模 43 的二次剩余！
整个过程我们只用到了加减乘除和取模，完全没有计算任何庞大的次幂，这就是二次互反定律的强大之处！

---

7. 为什么要学这个？（在CS中的应用）

很多学计算机的同学会问：这么底层的数学，对写代码有什么用？

1. 密码学基础：在公钥密码学中（如 RSA, Rabin密码体制），我们需要寻找大素数，或者求解模平方根。二次互反定律是判断方程 $x^2\equiv a(\mathrm{mod}p)$ 是否有解的最快理论工具。
2. 零知识证明 (ZKP)：在某些零知识证明协议（如证明自己拥有某个密钥但不泄露）中，经常利用“抛硬币”协议，而基于二次剩余的抛硬币协议完全依赖于勒让德符号和雅可比符号（勒让德符号的推广）的计算。
3. 算法优化：结合欧几里得算法，计算雅可比符号（基于二次互反定律）的时间复杂度仅为 $O(\log a\cdot \log p)$，这是一种极高效率的算法模式，经常在安全协议的设计中被复用。

8. 总结

希望文章有用，求赞求收藏求关注！！！！！！！！