Appearance
第 5 章：原根和离散对数
先别被"原根"这个词吓住。
想象你有一个数字，你不停地把它乘方：a¹, a², a³, a⁴...
这些幂次 mod m 的余数会怎么变？
有的数会很"短命"——比如模 7 下，2¹=2, 2²=4, 2³=1，才 3 次就回到 1 了，后面只是循环。这个 3 就叫 2 的阶。
有的数则很"长命"——比如模 7 下，3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1，把所有非零余数都逛了一遍才回来。这种能"逛遍全场"的数就叫原根。
一、阶：第一次回到 1 要几次方
设 gcd(a, m) = 1。不断算 a¹, a², a³, ... mod m，第一次出现 aᵈ ≡ 1 (mod m) 的时候，d 就是 a 的阶，记作 ordₘ(a)。
例题：求 ord₇(2)
gcd(2, 7) = 1，可以谈阶。一个个算：
| 幂 | mod 7 |
|---|---|
| 2¹ | 2 |
| 2² | 4 |
| 2³ | 8 ≡ 1 ← 第一次回到 1！ |
所以 ord₇(2) = 3。
费马小定理说 2⁶ ≡ 1 (mod 7)，但阶是 3
因为阶要的是"第一次"回到 1。6 也是对的，但不是最小的那个。阶一定是 φ(m) 的因数——3 是 6 的因数，没错。
阶的一条铁律
阶一定是 φ(m) 的因数。
比如模 7，φ(7) = 6，所以任何数的阶只能是 1, 2, 3, 6。绝不可能出现 4 或 5。
这条铁律超级实用——它可以让你少算很多不必要的幂次。
二、原根：每个可逆元素都能被它"生成"
如果 ordₘ(g) = φ(m)——阶达到了最大可能值——那 g 就是模 m 的原根。
这有什么了不起？因为 g 的幂次 g¹, g², ..., g^φ(m) 会恰好跑遍所有和 m 互素的余数，一个不漏、一个不重。
原根 = 能"生成"整个简化剩余系的数。
例题：2 是模 5 的原根吗？
模 5 的简化剩余系是 {1, 2, 3, 4}，φ(5) = 4。
算 2 的幂：
| 幂 | mod 5 |
|---|---|
| 2¹ | 2 |
| 2² | 4 |
| 2³ | 8 ≡ 3 |
| 2⁴ | 16 ≡ 1 ← 第一次回到 1 |
ord₅(2) = 4 = φ(5)，而且生成的序列 {2, 4, 3, 1} 恰好是所有可逆元素。
所以 2 是模 5 的原根。
三、最重要的公式：用原根算任意元素的阶
如果 g 是模 m 的原根，那任意可逆元素 gᵏ 的阶可以秒算：
ordₘ(gᵏ) = φ(m) / gcd(φ(m), k)
这一条公式是第 5 章综合题的命脉。后面求指定阶元素、求全部原根，全靠它。
四、已知一个原根，怎么找到所有原根？
如果一个 g 是原根，那么所有原根都可以写成 gᵏ 的形式，其中：
1 ≤ k ≤ φ(m)，且 gcd(k, φ(m)) = 1
为什么？套上面那条公式：要让 ord(gᵏ) = φ(m)，就需要 gcd(φ(m), k) = 1。
例题：模 5 的全部原根
已知 2 是模 5 的原根，φ(5) = 4。
找 1~4 中和 4 互素的 k：k = 1, 3。
| k | 2ᵏ mod 5 |
|---|---|
| 1 | 2 |
| 3 | 8 ≡ 3 |
所以模 5 的全部原根是：{2, 3}。
例题：模 22 的全部原根
已知模 22 有原根，且 7 是一个原根。φ(22) = 10。
找 1~10 中和 10 互素的 k：
| k | gcd(k, 10) | 留？ |
|---|---|---|
| 1 | 1 | ✓ |
| 2 | 2 | ✗ |
| 3 | 1 | ✓ |
| 4 | 2 | ✗ |
| 5 | 5 | ✗ |
| 6 | 2 | ✗ |
| 7 | 1 | ✓ |
| 8 | 2 | ✗ |
| 9 | 1 | ✓ |
| 10 | 10 | ✗ |
k = 1, 3, 7, 9。
算 7ᵏ mod 22：
| k | 7ᵏ mod 22 |
|---|---|
| 1 | 7 |
| 3 | 7³ = 343 ≡ 13 |
| 7 | 7⁷ ≡ 17 |
| 9 | 7⁹ ≡ 19 |
全部原根：{7, 13, 17, 19}。
五、列出指定阶的元素——期末综合题最爱考的
套路：已知 g 是原根，要求阶为某个值 d 的所有元素。
核心公式：
ordₘ(gᵏ) = φ(m) / gcd(φ(m), k)
设你要阶为 d，那就是：
φ(m) / gcd(φ(m), k) = d
所以 gcd(φ(m), k) = φ(m) / d
然后你找出所有 k 满足这个 gcd 条件，再算 gᵏ mod m 就行。
例题：模 17 下，阶为 8 的所有整数
已知 5 对模 17 的阶为 16（即 5 是原根，φ(17)=16）。
我们要 ord₁₇(5ᵏ) = 8，即：
16 / gcd(16, k) = 8
gcd(16, k) = 2
在 1~16 中，找和 16 的 gcd = 2 的 k：
| k | gcd(16, k) | 满足？ |
|---|---|---|
| 2 | 2 | ✓ |
| 4 | 4 | ✗ |
| 6 | 2 | ✓ |
| 8 | 8 | ✗ |
| 10 | 2 | ✓ |
| 12 | 4 | ✗ |
| 14 | 2 | ✓ |
| 16 | 16 | ✗ |
k = {2, 6, 10, 14}。
算 5ᵏ mod 17：
| k | 5ᵏ mod 17 |
|---|---|
| 2 | 5² = 25 ≡ 8 |
| 6 | 2 |
| 10 | 9 |
| 14 | 15 |
答案：{2, 8, 9, 15}。顺序随意。
再练一道：模 41 下，阶为 8 的所有整数
已知 6 是模 41 的原根（ord₄₁(6) = 40 = φ(41)）。
要求 ord₄₁(6ᵏ) = 8：
40 / gcd(40, k) = 8
gcd(40, k) = 5
1~40 中 gcd(40, k) = 5 的：k = 5, 15, 25, 35。
| k | 6ᵏ mod 41 |
|---|---|
| 5 | 27 |
| 15 | 3 |
| 25 | 14 |
| 35 | 38 |
答案：{3, 14, 27, 38}。
六、已知阶，速算大幂
如果已知 ordₘ(a) = d，那 aᵈ ≡ 1。指数可以按 d 来降，和费马/欧拉的思路一样。
例题：已知 ord₄₁(18) = 5，求 18¹⁸ mod 41
18⁵ ≡ 1 (mod 41)。
把 18 按 5 拆：
18 = 5×3 + 3
18¹⁸ = (18⁵)³ × 18³ ≡ 1³ × 18³ ≡ 18³ (mod 41)
算 18³：
18² = 324 ≡ 37 (mod 41)（324 - 41×7 = 37）
18³ = 37 × 18 = 666 ≡ 10 (mod 41)（666 - 41×16 = 10）
答案：18¹⁸ ≡ 10 (mod 41)。
七、离散对数：正着容易，反着难
指数运算：已知 x，算 gˣ mod p。这是正着算，用平方表几秒搞定。
离散对数：已知 y = gˣ mod p，倒着求 x。记作 x = ind_g(y)。这是反着求，没有捷径，只能暴力搜，当 p 很大时基本算不出来。
密码学（比如 Diffie-Hellman、ElGamal）的安全性就建立在这一点上：
正着算（求幂）像坐滑梯下楼，反着求（离散对数）像徒手爬悬崖。
期末最多考概念，不考你手算大模数的离散对数。记住它跟"普通对数"的类比关系就行。
本章做题速查表
| 看到什么 | 立刻想 |
|---|---|
| 求 ordₘ(a) | 从 a¹ 开始算，第一次回到 1 的指数 |
| 判断 g 是不是原根 | ordₘ(g) = φ(m)？ |
| 已知原根 g，求全部原根 | gᵏ，gcd(k, φ(m)) = 1 |
| 求阶为 d 的所有元素 | φ(m)/gcd(φ(m),k) = d → 找 k → 算 gᵏ |
| 已知阶，求大幂 | 指数按阶来降（a^阶 ≡ 1） |
| 离散对数 | 正算容易反算难（密码学基础） |
最容易翻车的地方
- 阶 ≠ φ(m)。阶是最小的那个指数，不是 φ(m) 本身。比如 ord₇(2) = 3，不是 6。
- 忘了原根不一定存在。原根存在的前提是模数为 2, 4, pᵏ, 2pᵏ（p 奇素数）。模 15 之类的就没有原根——不过期末一般给的模数都有。
- 公式的分母分不清：ord(gᵏ) = φ(m) / gcd(φ(m), k)，是 φ(m) 在上、gcd 在下，别倒过来。
- 找指定阶元素时，k 的范围忘了取到 φ(m)。k 从 1 到 φ(m)，不是 1 到 m-1。
- 阶必须是 φ(m) 的因数。算出来不是因数的肯定是算错了。
自测题
- 求 ord₇(2)。
- 写出模 5 的全部原根。
- 已知模 22 有原根，求模 22 的所有原根。
- 已知 5 对模 17 的阶为 16，列出模 17 下所有阶为 8 的整数。
- 已知 ord₄₁(18) = 5，求 18¹⁸ mod 41。
自测答案
- ord₇(2) = 3。
- {2, 3}。
- φ(22) = 10，取 k = 1, 3, 7, 9，得 {7, 13, 17, 19}。
- {2, 8, 9, 15}。
- 18¹⁸ ≡ 18³ ≡ 10 (mod 41)。