引言
hello！欢迎回到咪猫魔法世界~ 🐾✨
信安人绕不开的“数论坎”来啦！前面学完一次同余方程，本以为可以顺风顺水，结果碰到二次同余直接懵圈——怎么一次到二次，解法复杂度直接翻倍啊？！
这篇blog是上一篇《信安数学基础学习与练习》的专项补强，专门拆解二次同余方程、二次剩余、勒让德符号这些“拦路虎”，还会和一次同余做详细对比，帮大家理清逻辑。全程保持真实踩坑感，毕竟“懂（不）了”才是学习数论的常态嘛！
一、二次同余方程：从一次到二次解法的“蜕变”
一次同余方程靠扩展欧几里得就能直接冲，可二次同余完全不一样！核心逻辑是“拆解+合并”，先把复杂模数拆成简单素数幂，解完再用中国剩余定理合并，一步都不能省。
1.1 二次同余方程核心原理
二次同余方程的一般形式是 \(ax^2 + bx + c \equiv 0 \pmod{m}\)，最简形式是 \(x^2 \equiv a \pmod{m}\)（a、m为整数，\(m>0\)）。
核心思路就两步：
- 模数分解：根据“素数幂分解定理”，把m拆成 \(m = p_1^{k_1} \times p_2^{k_2} \times ... \times p_n^{k_n}\)（\(p_i\) 是素数）；
- 合并解：原方程等价于“模每个素数幂 \(p_i^{k_i}\) 的同余方程组”，解完每个方程组后，用中国剩余定理合并出最终解。
Q: 为啥要这么拆？ A: 直接解模合数m的方程太难了！素数幂的方程更简单，拆解后难度直接降级🐱
1.2 一次 vs 二次同余方程
为了避免混淆，我把两者的关键差异整理成了表格，一目了然：
| 对比维度 | 一次同余方程 | 二次同余方程 |
|---|---|---|
| 方程形式 | \(ax \equiv b \pmod{m}\)（a、m为整数，\(m>0\)） | 一般形式：\(ax^2 + bx + c \equiv 0 \pmod{m}\)；最简形式：\(x^2 \equiv a \pmod{m}\) |
| 解的存在性判断 | 简单！计算\(\gcd(a,m)\)，若能整除b则有解 | 复杂！先拆m为素数幂，再用勒让德符号/欧拉判别法判断每个素数幂下是否有解，最后看所有方程组是否都有解 |
| 核心解法工具 | 1. 扩展欧几里得算法（求特解）；2. 中国剩余定理（合并解） | 1. 勒让德/雅可比符号（判断可解性）；2. 亨泽尔引理（提升素数解到素数幂解）；3. Tonelli-Shanks算法（求素数模下的解）；4. 中国剩余定理（合并解） |
| 解的数量与结构 | 若有解，设\(d=\gcd(a,m)\)，则模m下有d个不同解；解的结构：\(x \equiv x_0 + k \times m/d \pmod{m}\)（\(k=0,1,...,d-1\)），规律明确 | 模素数p（\(p \nmid a\)）：有解则通常2个解；\(x^2 \equiv 0 \pmod{p}\) 仅有1个解\(x \equiv 0\)；模素数幂\(p^k\)：解数可能为0、1或2；模合数m：解数是各素数幂解数的乘积，无统一规律 |
| 复杂度与应用 | 复杂度低，直接用于RSA求模逆元等场景 | 复杂度高，依赖大数分解；二次剩余的判断困难性是Goldwasser-Micali概率加密的安全基础，求解算法（如Tonelli-Shanks）用于椭圆曲线密码 |
二、二次剩余：平方同余有解的“专属名字”
搞懂二次同余，核心就是搞懂“二次剩余”——本质就是判断“\(x^2 \equiv a \pmod{p}\) 有没有解”
2.1 二次剩余的定义
- 若存在某个x，使得 \(x^2 \equiv a \pmod{p}\) 成立，就称“a是模p的二次剩余”；
- 若对任意x都不成立，就称“a是模p的二次非剩余”；
- 0既不是二次剩余，也不是二次非剩余。
2.2 核心性质：分布对称+数量半分
这两个性质是二次剩余的“灵魂”，记住就能快速理解其规律：
- 平方的对称性：对任意 \(x \in \{1,2,...,p-1\}\)，都有 \(x^2 \equiv (p-x)^2 \pmod{p}\)。比如\(p=7\)时，\(2^2 \equiv 5^2 \equiv 4 \pmod{7}\)，平方数都是成对出现的～
- 数量的半分性：模p的缩系（即\(1,2,...,p-1\)）共有\(p-1\)个数，因为平方数成对，所以二次剩余和二次非剩余的数量各占一半，都是\((p-1)/2\)。比如\(p=5\)时，缩系是\(\{1,2,3,4\}\)，二次剩余是1、4（2个），非剩余是2、3（2个）。
2.3 与二次同余的关联
二次同余方程的核心是“平方项可解性”，而二次剩余的定义就是“平方同余有解”的直接表述。通过配方化简和模数分解，二次同余方程的可解性，完全等价于“某个数是否为二次剩余”——简单说，二次剩余存在，方程才有解！
三、判断二次剩余：3种方法从暴力到高效
知道了二次剩余的定义，怎么判断一个数是不是二次剩余呢？我整理了3种常用方法，从简单到高效，大家可以按需选择~o( =∩ω∩= )m～
3.1 暴力验证（枚举法）
- 原理：直接枚举模p的缩系\(\{1,2,...,p-1\}\)，计算每个数的平方模p，看是否等于a；
- 适用场景：只适用于小质数p（比如\(p<1000\)），时间复杂度\(O(p)\)，p太大就跑不动了。
3.2 欧拉判别法（核心理论）
- 原理：对奇素数p和整数a（\(p \nmid a\)），计算 \(a^{(p-1)/2} \pmod{p}\)：
- 若结果\(\equiv 1\)，则a是模p的二次剩余；
- 若结果\(\equiv -1\)，则a是模p的二次非剩余；
- 依据：费马小定理（\(a^{p-1} \equiv 1 \pmod{p}\)）+ 二次剩余的平方幂性质；
- 优势：比枚举法高效，大p也能用，但需要快速幂优化指数运算。
3.3 勒让德符号（结合二次互反律，最高效）
欧拉判别法虽然好用，但复杂运算时不够简便，勒让德符号就是为了解决这个问题。
3.3.1 勒让德符号的定义
设p是素数，定义勒让德符号 \(\left(\frac{a}{p}\right)\)：
\[ \left(\frac{a}{p}\right)= \begin{cases} 1, & 若a是模p的二次剩余； \\ -1, & 若a是模p的二次非剩余； \\ 0, & 若p \mid a。 \end{cases} \]简单说：\(\left(\frac{a}{p}\right)=1\) 等价于 \(x^2 \equiv a \pmod{p}\) 有解；\(\left(\frac{a}{p}\right)=-1\) 等价于无解。
3.3.2 关键计算规则⭐
- 可乘性：\(\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right)\)，能把a分解成素数乘积后逐因子计算；
- 模约简：若 \(a \equiv b \pmod{p}\)，则 \(\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)\)；
- 二次互反律：对不同的奇素数p、q，有 \(\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}\)，能把模大质数的判断转化为模小质数的判断；
- 特殊值公式：
- \(\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}\)；
- \(\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}\)。
核心优势：通过“可乘性+模约简+二次互反律”递归简化计算，不用枚举也不用算复杂指数，效率拉满。
四、二次剩余的求解方法：从特殊到通用
判断出a是模p的二次剩余后，怎么求x呢？这里为大家分享3种常用方法，可覆盖不同场景。
4.1 特殊值法（特定模数快速解）
针对两种特殊模数，有“傻瓜公式”直接套用，不用复杂计算：
- 当 \(p \equiv 3 \pmod{4}\) 时：解为 \(x \equiv \pm a^{\frac{p+1}{4}} \pmod{p}\)（前面的文章里详细讲过，这里不多赘述了）；
- 当 \(p \equiv 5 \pmod{8}\) 且 \(a^2 \equiv 2 \pmod{p}\) 时：解为 \(x \equiv \pm a^{\frac{p+3}{8}} \pmod{p}\)，也可结合2的幂次调整，快速算出结果。
4.2 Tonelli-Shanks算法（通用高效）
这是最常用的二次剩余通用求解算法，任意奇素数p的二次剩余都能解，时间复杂度 \(O(\log^2 p)\)，步骤如下：
- 分解模数减一：把 \(p-1\) 拆成 \(q \cdot 2^s\)（q为奇数）；
- 找二次非剩余：随机选整数z，直到z是模p的二次非剩余（成功概率约50%，很快就能找到）；
- 初始化参数：令 \(m=s\)，\(c=z^q \pmod{p}\)，\(t=a^q \pmod{p}\)，\(r=a^{\frac{q+1}{2}} \pmod{p}\)；
- 迭代调整：重复直到 \(t \equiv 1 \pmod{p}\)：
- 找到最小的i（\(0
- 令 \(b=c^{2^{m-i-1}} \pmod{p}\)，更新 \(m=i\)、\(c=b^2 \pmod{p}\)、\(t=t \cdot c \pmod{p}\)、\(r=r \cdot b \pmod{p}\)；
- 找到最小的i（\(0
- 输出解：r是一个解，另一个解是 \(p-r\)（模p下）。
4.3 Cipolla算法（涉及扩域思想）
思路很巧妙，通过“构造扩域”把二次剩余求解转化为扩域中的幂运算，时间复杂度和快速幂相当，适合算法竞赛等对效率要求高的场景：
- 构造扩域：随机选整数a，使得 \(a^2 - n\) 是模p的二次非剩余（成功概率约50%），定义扩域 \(\mathbb{F}_p[i] = \{x + yi \mid x,y \in \mathbb{F}_p\}\)，其中 \(i^2 \equiv a^2 - n \pmod{p}\)；
- 扩域幂运算：计算 \((a+i)^{\frac{p+1}{2}} \pmod{p}\)（按多项式乘法规则计算）；
- 提取实部：由于扩域的特殊性质，这个幂运算的虚部系数为0，实部就是 \(x^2 \equiv n \pmod{p}\) 的一个解，另一个解是 \(p-实部\)。
✨ 咪猫碎碎念
二次剩余和勒让德符号真的是“入门难，理解后就通了”的知识点～ 核心就是记住“判断可解性（勒让德符号）+ 求解（Tonelli-Shanks/Cipolla）”的流程，再结合二次同余方程的“拆解+合并”思路，数论这部分就拿下大半啦！
虽然过程中无数次想放弃，但啃懂后真的很有成就感～ 不过学数论确实没有捷径，多做题多推导，慢慢就上手了！
参考blog