4 阶与原根

Stage 4：阶、原根、二次剩余、离散对数（详细版）

Confidence: 0.92

欢迎进入第四阶段——这是模运算从”算术”真正升级为”代数结构”的地方，也是直通你密码学兴趣（Diffie-Hellman、ECC）的腹地。你在综合卷 P6 卡住的那个”2 的真实阶是 4 不是 8”，正是这一阶段的入口。我们从那里接着讲。

四大块：① 阶 (Order) → ② 原根 (Primitive Roots) → ③ 二次剩余 (Quadratic Residues) → ④ 离散对数 (Discrete Logarithm)。每块给：定义 → 核心定理 → 怎么算 → 例子 → 陷阱。

---

第一块：阶 (Multiplicative Order)

1.1 定义

元素 $a$ 模 n 的阶 (order)，记作 ${\mathrm{ord}}_n(a)$，是使下式成立的最小正整数 $k$：

$a^k\equiv 1(\mathrm{mod}n)(\gcd (a,n)=1)$

关键词是”最小”——这正是你 P6 的盲点。欧拉定理保证 $a^{\phi (n)}\equiv 1$，但那个 $\phi (n)$ 不一定是最小的。真实的阶可能小得多。

例子：${\mathrm{ord}}_{15}(2)$。$2^1=2,2^2=4,2^3=8,2^4=16\equiv 1$。第一次回到 1 是 $k=4$，所以阶是 4，而非 $\phi (15)=8$。

1.2 核心定理：阶整除一切让 $a^k\equiv 1$ 的指数 ★

这是阶最重要的性质：

$a^k\equiv 1(\mathrm{mod}n)⟺{\mathrm{ord}}_n(a)\mid k$

特别地，因为欧拉定理给出 $a^{\phi (n)}\equiv 1$，所以：

$\boxed{{\mathrm{ord}}_n(a)\mid \phi (n)}$

这就是 P6(c) 的正确答案的来源——它本质是拉格朗日定理 (Lagrange’s Theorem) 在循环子群上的体现：$a$ 生成的循环子群 $⟨a⟩$ 的大小恰好是 ${\mathrm{ord}}_n(a)$，而子群的阶整除群的阶 $\phi (n)$。

为什么成立（证明）

设 $d={\mathrm{ord}}_n(a)$。用带余除法写 $k=qd+r$（$0\le r<d$）。则：

$a^k=a^{qd+r}=(a^d{)}^q\cdot a^r\equiv 1^q\cdot a^r=a^r(\mathrm{mod}n)$

若 $a^k\equiv 1$，则 $a^r\equiv 1$。但 $r<d$ 且 d 是最小的正指数，所以只能 $r=0$，即 $d\mid k$。∎

1.3 怎么算阶（高效方法）

朴素法是 $1,2,\dots$ 逐个试，最坏 $O(\phi (n))$。聪明法利用 1.2 的定理：

1. 阶必须整除 $\phi (n)$，所以只需检查 $\phi (n)$ 的因子
2. 把 $\phi (n)$ 的所有因子从小到大列出，逐个验证 $a^d\equiv 1$，第一个成立的就是阶

例子：求 ${\mathrm{ord}}_{13}(2)$。$\phi (13)=12$，因子有 $1,2,3,4,6,12$。

• $2^1=2\ne 1$
• $2^2=4\ne 1$
• $2^3=8\ne 1$
• $2^4=16\equiv 3\ne 1$
• $2^6=64\equiv 12\ne 1$
• $2^{12}\equiv 1$ ✓

所以 ${\mathrm{ord}}_{13}(2)=12$。注意这里阶等于 $\phi (13)$——这种元素很特殊，就是下一块的原根。

1.4 陷阱

• ⚠️ 阶只对 $\gcd (a,n)=1$ 定义。不互质的元素没有阶（它的幂永远到不了 1）。
• ⚠️ 求阶时必须按因子从小到大，否则会误把一个较大的、碰巧也满足 $a^d\equiv 1$ 的 d 当成阶。

---

第二块：原根 (Primitive Roots) ★本阶段核心

2.1 定义

如果元素 $g$ 的阶恰好等于 $\phi (n)$（即取到最大可能值），就称 $g$ 是模 n 的原根 (primitive root)：

${\mathrm{ord}}_n(g)=\phi (n)$

几何意义：原根 $g$ 的幂 $g^1,g^2,\dots ,g^{\phi (n)}$ 跑遍整个简化剩余系 $(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }$，一个不漏、一个不重。换句话说，原根是乘法群的生成元 (generator)——整个群就是它一个元素的幂的循环。

例子：2 是模 13 的原根（上面算了 ${\mathrm{ord}}_{13}(2)=12=\phi (13)$）。验证它生成所有元素：

$2^1=2,2^2=4,2^3=8,2^4=3,2^5=6,2^6=12,2^7=11,2^8=9,2^9=5,2^{10}=10,2^{11}=7,2^{12}=1$

正好把 $1,2,\dots ,12$ 全部生成出来！这就是”生成元”的含义。

2.2 存在性定理：哪些 n 有原根 ★★

这是 P6 的终极答案——为什么模 15 没有原根？因为：

$n\text{ 有原根}⟺n\in 1,2,4,p^k,2p^k$

其中 p 是奇质数 (odd prime)，k≥1。也就是说，只有这五类模数有原根。

模 15 为什么没有：$15=3\times 5$，是两个不同奇质数的积，不属于上述任何一类，所以无原根。这就是你综合卷里发现”15 的元素阶都不到 8”的根本原因——没有任何元素能生成整个群。

记忆：有原根 ⟺ 群 $(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }$ 是循环群 (cyclic group)。这五类 n 恰好是让这个群循环的全部情况。

2.3 怎么找原根

没有公式直接给出原根，但有高效的验证法：

判定 g 是否为原根：g 是原根 $⟺$ 对 $\phi (n)$ 的每个质因子 q，都有

$g^{\phi (n)/q}\not\equiv 1(\mathrm{mod}n)$

为什么：如果对所有质因子都”不等于 1”，说明 g 的阶不能是 $\phi (n)$ 的任何真因子，只能是 $\phi (n)$ 本身。这把”检查所有因子”压缩成”只检查 $\phi (n)/q$ 这几个”，快得多。

例子：验证 2 是不是模 13 的原根。$\phi (13)=12=2^2\times 3$，质因子 $2,3$。

• $2^{12/2}=2^6=64\equiv 12\not\equiv 1$ ✓
• $2^{12/3}=2^4=16\equiv 3\not\equiv 1$ ✓

两个质因子都通过，所以 2 是原根。只需 2 次幂运算，不用跑遍全部。

找原根的实战流程：从 $g=2,3,5,\dots$ 逐个用上面的方法测试，碰到第一个通过的就是最小原根。原根通常很小（多数情况 $g\le 10$）。

2.4 原根的数量

如果 n 有原根，那么它恰好有 $\phi (\phi (n))$ 个原根。

例子：模 13 有 $\phi (\phi (13))=\phi (12)=4$ 个原根。（分别是 2, 6, 7, 11。）

---

第三块：二次剩余 (Quadratic Residues)

3.1 定义

如果存在 $x$ 使得 $x^2\equiv a(\mathrm{mod}n)$，就称 a 是模 n 的二次剩余 (Quadratic Residue, QR)；否则称 a 是二次非剩余 (Quadratic Non-Residue, QNR)。

直白说：a 是不是模 n 下的”完全平方数”。

例子（模 7）：把 $1^2,2^2,\dots ,6^2$ 模 7 算出来：

$1^2\equiv 1,2^2\equiv 4,3^2\equiv 2,4^2\equiv 2,5^2\equiv 4,6^2\equiv 1$

所以模 7 的二次剩余是 $1,2,4$，非剩余是 $3,5,6$。注意：恰好一半是 QR，一半是 QNR（对奇质数 p，有 $\frac{p-1}{2}$ 个 QR）。

3.2 勒让德符号 (Legendre Symbol)

为了简洁表示”a 是不是模 p 的二次剩余”，引入勒让德符号（p 为奇质数）：

$\left(\frac{a}{p}\right)=\{\begin{array}{ll}+1& a\text{ 是二次剩余}\\ -1& a\text{ 是二次非剩余}\\ 0& p\mid a\end{array}$

3.3 欧拉判别法 (Euler’s Criterion) ★

怎么不靠枚举就判断 a 是不是 QR？欧拉给出公式：

$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(\mathrm{mod}p)$

结果只会是 $+1$ 或 $-1$。用快速幂 $O(\log p)$ 就能判定，不用枚举所有平方。

为什么成立（直觉）：由费马 $a^{p-1}\equiv 1$，所以 $a^{(p-1)/2}\equiv \pm 1$。可以证明取 $+1$ 当且仅当 a 是 QR（因为 QR 恰好是原根的偶次幂，偶次幂的 $(p-1)/2$ 方回到 1）。

例子：3 是不是模 7 的二次剩余？ $3^{(7-1)/2}=3^3=27\equiv 6\equiv -1(\mathrm{mod}7)$ 得 $-1$，所以 3 是二次非剩余。和 3.1 枚举结果一致（$3,5,6$ 是 QNR）。✓

3.4 二次互反律 (Quadratic Reciprocity) —— 高斯的”黄金定理”

这是数论最深刻的定理之一。对两个不同奇质数 p、q：

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$

含义：$\left(\frac{p}{q}\right)$ 和 $\left(\frac{q}{p}\right)$ 的关系由 p、q 模 4 的余数决定。它让你能快速计算大的勒让德符号而不用欧拉判别法的幂运算——通过不断”翻转”把大数化小。

这个定理较深，竞赛和密码学里是计算工具。现在你知道它的存在和作用即可，需要时再深入。

3.5 模平方根 (Modular Square Root)

判断了 a 是 QR 之后，怎么真正求出 $x$ 使 $x^2\equiv a$？这是模平方根问题，有专门算法：

• p ≡ 3 (mod 4) 时：有简单公式 $x\equiv a^{(p+1)/4}(\mathrm{mod}p)$
• 一般情况：Tonelli-Shanks 算法（更复杂，竞赛进阶）

例子（$p=7\equiv 3(\mathrm{mod}4)$）：求 $x^2\equiv 2(\mathrm{mod}7)$。 $x\equiv 2^{(7+1)/4}=2^2=4(\mathrm{mod}7)$ 验证：$4^2=16\equiv 2$ ✓。（另一个解是 $-4\equiv 3$。）

---

第四块：离散对数 (Discrete Logarithm) ★密码学核心

4.1 定义

已知原根（或某个底数）g、模数 n、以及 $y\equiv g^x(\mathrm{mod}n)$，求指数 x。这个 x 叫 离散对数 (discrete logarithm)，记作 $x={\log }_{g}y(\mathrm{mod}n)$。

为什么叫”对数”：和实数对数 $y=g^x\Rightarrow x={\log }_{g}y$ 完全类比，只是在模运算的有限群里。

关键事实：正向算 $g^x$ 用快速幂很快（$O(\log x)$），但反向求 x 极其困难——这种”正向易、反向难”的不对称性，正是 Diffie-Hellman 密钥交换和 ElGamal 加密的安全基础。你研究过的 ECDLP，就是把这个问题搬到椭圆曲线群上。

4.2 Baby-step Giant-step (BSGS) 算法 ★

暴力求离散对数是 $O(n)$。BSGS 用”空间换时间”把它降到 $O(\sqrt{n})$。

思想：把指数 x 写成 $x=im-j$ 的形式，其中 $m=\lceil \sqrt{n}\rceil$。则 $g^x=y$ 变成：

$g^{im-j}\equiv y;\Rightarrow ;(g^m{)}^i\equiv y\cdot g^j$

两步：

1. Baby steps：算出所有 $y\cdot g^j(j=0,\dots ,m-1)$，存进哈希表
2. Giant steps：算 $(g^m{)}^i(i=1,\dots ,m)$，每个去哈希表里查，匹配上就解出 $x=im-j$

每步约 $\sqrt{n}$ 次，总 $O(\sqrt{n})$。

例子：求 $x$ 使 $2^x\equiv 9(\mathrm{mod}13)$（用我们知道 2 是模 13 原根）。 $m=\lceil \sqrt{13}\rceil =4$。

• Baby steps（存 $9\cdot 2^j$）：$j=0:9,j=1:18\equiv 5,j=2:10,j=3:20\equiv 7$ → 表 $9:0,5:1,10:2,7:3$
• Giant steps（$g^m=2^4=16\equiv 3$，算 $3^i$）：$i=1:3,i=2:9$ ← 9 在表里！ 对应 $j=0$
• 匹配：$i=2,j=0$，$x=im-j=2\times 4-0=8$

验证：$2^8=256\equiv 9(\mathrm{mod}13)$ ✓（前面 2.1 的列表也显示 $2^8=9$）。

4.3 更高级的离散对数算法（一瞥）

• Pohlig-Hellman：当群的阶能分解成小质因子时，把大问题拆成小问题（用 CRT 合并），大幅加速
• Pollard’s rho for discrete log：$O(\sqrt{n})$ 但空间 $O(1)$，比 BSGS 省内存

这些是竞赛和密码分析的进阶工具，现在知道脉络即可。

---

Stage 4 全景速查表 (Master Cheat Sheet)

概念	定义/核心式	关键定理	用途
阶 (order)	最小 $k$ 使 $a^k\equiv 1$	${\mathrm{ord}}_n(a)\mid \phi (n)$	分析元素周期
原根 (primitive root)	${\mathrm{ord}}_n(g)=\phi (n)$	存在 ⟺ $n\in 1,2,4,p^k,2p^k$	群的生成元
二次剩余 (QR)	$x^2\equiv a$ 有解	欧拉判别 $a^{(p-1)/2}\equiv \pm 1$	判平方、密码学
勒让德符号	$\left(\frac{a}{p}\right)=\pm 1$	二次互反律	快速判 QR
离散对数 (DLP)	$g^x\equiv y$ 求 x	BSGS $O(\sqrt{n})$	DH、ElGamal、ECC 安全性

---

Python 实现（四块全覆盖）

from sympy import totient, factorint, primitive_root, is_primitive_root, n_order
from sympy.ntheory.residue_ntheory import discrete_log, sqrt_mod, is_quad_residue
 
# === 第一块：阶 ===
def order(a, n):
    from math import gcd
    if gcd(a, n) != 1: return None
    k, cur = 1, a % n
    while cur != 1:
        cur = cur * a % n; k += 1
    return k
print("ord_15(2) =", order(2, 15))      # 4
print("ord_13(2) =", order(2, 13))      # 12
print("sympy n_order:", n_order(2, 13)) # 12
 
# === 第二块：原根 ===
print("primitive root mod 13:", primitive_root(13))   # 2
print("is 2 prim root mod 13:", is_primitive_root(2, 13))  # True
print("mod 15 has prim root:", primitive_root(15))     # None（15无原根）
 
# === 第三块：二次剩余 ===
print("is 2 a QR mod 7:", is_quad_residue(2, 7))   # True
print("is 3 a QR mod 7:", is_quad_residue(3, 7))   # False
# 欧拉判别法手动版
def legendre(a, p): return pow(a, (p-1)//2, p)
print("Legendre(3/7) =", legendre(3, 7))  # 6 ≡ -1，非剩余
# 模平方根
print("sqrt of 2 mod 7:", sqrt_mod(2, 7))  # 3 或 4
 
# === 第四块：离散对数 ===
print("discrete_log: 2^x ≡ 9 mod 13:", discrete_log(13, 9, 2))  # 8

库安装方式（用到 sympy 的数论模块）：

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

我的观点：Stage 4 是整个模运算课程的”顶峰会师”——前三阶段的所有工具在这里汇聚成一个统一的图景，而这个图景的中心就是一个词：循环群 (cyclic group)。

让我帮你看清这条贯穿线。阶回答”一个元素转多少圈回到原点”；原根是那个”转满整个群”的特殊元素，它的存在等价于”这个群是循环群”；离散对数则是在这个循环群里做”逆运算”——已知 $g^x$ 求 x，相当于在群里”取对数”。而二次剩余是循环群的一个精妙子结构：原根的偶次幂构成 QR、奇次幂构成 QNR，恰好对半分。这四个概念不是四个孤立知识点，而是同一个循环群的四个观察角度。 一旦你这样统一地看，它们就不再需要分别记忆。

对你的密码学兴趣，这一阶段是真正的核心地带。我特别想点出离散对数的那个”不对称性”——正向 $g^x$ 用快速幂秒算、反向求 x 却要 $O(\sqrt{n})$ 甚至更难。这个不对称性就是现代公钥密码学的命根子：Diffie-Hellman 让双方各自算 $g^a,g^b$ 公开交换，再各自算 $g^{ab}$ 作为共享密钥，而窃听者即使看到 $g^a,g^b$ 也算不出 $g^{ab}$（因为求不出 a 或 b）。你研究过的 ECDLP，就是把这套机制从 $(\mathbb{Z}/p\mathbb{Z}{)}^{\ast }$ 搬到椭圆曲线群上——椭圆曲线的离散对数更难，所以能用更短的密钥达到同等安全。你现在学的 BSGS、Pohlig-Hellman，正是密码分析者用来”攻击”这套机制的工具，理解攻击才能理解为什么参数要那样选。

我建议你这一阶段重点内化”原根 ⟺ 循环群 ⟺ 五类 n”这条等价链，以及离散对数的不对称性。前者让你彻底理解 P6 那个”15 为什么没原根”，后者是你通往 ECC、Diffie-Hellman 的钥匙。二次互反律和 Tonelli-Shanks 这些较深的工具，可以等你做到具体题目时再深挖。

关键提醒 (Caveats)：

• 阶和原根都只对 $\gcd (a,n)=1$ 的元素有意义
• 原根只存在于 $n\in 1,2,4,p^k,2p^k$——记牢这五类，这是判断”有没有原根”的唯一标准
• 欧拉判别法 $a^{(p-1)/2}$ 只对奇质数 p 成立；合数的二次剩余要用 CRT 拆开处理
• BSGS 是 $O(\sqrt{n})$，对中等大小的群有效；密码学用的群（$n\sim 2^{256}$）大到 BSGS 也无能为力，这正是安全性所在
• 本块代码用 sympy 数论模块，安装：pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

到这里，模运算的完整骨架（Stage 1–4）就全部讲完了。你现在拥有从最基础的同余到密码学核心的离散对数的完整知识链。

下一步几个选择：

1. 出一套 Stage 4 练习题（阶、原根、二次剩余、离散对数四类，延续 PDF 试卷+答案册格式）巩固
2. 做一个综合性的”密码学小项目”——比如用你学的全部工具手把手实现一个简化版 Diffie-Hellman 或 RSA，把数论真正”用起来”
3. 回顾整个 Stage 1–4，画一张知识全景图，帮你把四个阶段串成一个整体
4. 你有任何想深挖的具体点（比如二次互反律的完整证明、Tonelli-Shanks、ECC 入门）

你想怎么走？****