Appearance
第 5 章：原根和离散对数
别被“原根”和“阶”这两个高级词吓住。
在模 m 的世界里，数字不断乘方（a¹, a², a³...），结果会像在操场上跑圈一样循环。
- 有的人跑两三步就回到起点了，这叫“短命鬼”。
- 有的人体力极其充沛，把所有能踩的格子全踩了一遍才回到起点，这个“跑全图的大佬”就叫原根。
这一章只考三件事：怎么算阶？怎么找原根？怎么按要求挑出特定阶的数？
一、阶（Order）：你几步能回到 1？
设 a 和 m 互素。你不断算 a¹, a², a³, ... mod m，第一次出现结果为 1 的那个指数 d，就叫 a 的阶，记作 ordm(a) = d。
🚨 考场开挂技巧：绝不瞎算！找 φ(m) 的因数
如果让你求 2 模 7 的阶，不要傻乎乎地 1次方、2次方、3次方一直算下去。
阶有一条铁律：阶必须是 φ(m) 的因数！ 模 7 的 φ(7) = 6。6 的因数只有：1, 2, 3, 6。 所以 2 的阶只可能是 1、2、3 或 6，绝不可能是 4 或 5！ 你只需要挑这几个指数来试：
2¹ = 2 2² = 4 2³ = 8 ≡ 1 ← 第一次回到 1，游戏结束！ 所以
ord7(2) = 3。
二、原根（Primitive Root）：跑遍全图的大佬
如果你算出一个数 g 的阶，恰好等于整个世界的格子数 φ(m)，那 g 就是模 m 的原根。 原根的威力在于：只要不停地对它求幂，它就能把模 m 下所有互素的数全部生成出来，一个不漏。
例题：判断 2 是模 5 的原根吗？
模 5 的 φ(5) = 4。我们来看看 2 的阶是不是 4。 （根据铁律，因数有 1, 2, 4）
2¹ = 2
2² = 4
2⁴ = 16 ≡ 1 （中间省略了 2³，因为 3 不是因数直接跳过） 第一次回到 1 的指数确实是 4。所以 2 是模 5 的原根。
三、已知一个原根，找“全部原根”（必考题型）
期末考试通常会大发慈悲，先告诉你“已知 2 是原根”，然后让你找出所有的原根。 怎么找？一句话口诀：
所有的原根都是
gᵏ，要求：k 必须和 φ(m) 互素！
满分例题：已知 7 是模 22 的一个原根，求全部原根。
第一步：算 φ(22)。
22 = 2 × 11，所以 φ(22) = 22 × (1/2) × (10/11) = 10。
第二步：找合格的指数 k。 在 1 到 10 里面，找跟 10 互素的数（即不能是偶数，不能是5）：
k 的合格名单：1, 3, 7, 9。
第三步：求出所有的原根（算 7ᵏ mod 22）。
k=1: 7¹ ≡ 7
k=3: 7³ = 343 ≡ 13 (mod 22)
k=7: 7⁷ = (7³)² × 7 ≡ 13² × 7 ≡ 169 × 7 ≡ 15 × 7 = 105 ≡ 17 (mod 22)
k=9: 7⁹ = 7⁷ × 7² ≡ 17 × 49 ≡ 17 × 5 = 85 ≡ 19 (mod 22)
答案：模 22 的全部原根是 {7, 13, 17, 19}。
四、💥 找“指定阶”的所有元素（本章最难，傻瓜解法）
题目套路：已知 g 是原根，要求你找出所有“阶刚好等于 d”的数。 书上教你用 gcd(φ(m), k) = φ(m)/d 去反推 k，考试一紧张绝对算错。 请用下面这个“倍数过滤法”，纯纯的机械操作，绝不翻车！
傻瓜三步法：
- 算步长：步长 S = φ(m) / 目标阶数 d。
- 列名单：列出
1×S, 2×S, 3×S ... d×S，这就是候选的 k。 - 查户口（过滤）：只保留乘数（1,2,3...）和 d 互素的那些 k，带入
gᵏ计算即可！
实战演练 1：模 17 下，求阶为 8 的所有元素。
已知条件：模数 17，φ(17) = 16。题目已知 5 是原根。目标阶 d = 8。
- 第一步：算步长 S。
S = 16 ÷ 8 = 2。
- 第二步：列出候选 k（用步长 2 乘以 1 到 d）。
候选 k：1×2, 2×2, 3×2, 4×2, 5×2, 6×2, 7×2, 8×2。
- 第三步：过滤！只看乘数（1到8），谁跟目标阶 d(8) 互素？
跟 8 互素的只有：1, 3, 5, 7。
所以最终合格的 k 就是：1×2=2, 3×2=6, 5×2=10, 7×2=14。
- 终局计算：算
5ᵏ mod 17。5² = 25 ≡ 8
5⁶ = (5²)³ ≡ 8³ = 512 ≡ 2
5¹⁰ = 5⁶ × 5⁴ ≡ 2 × 8² ≡ 2 × (-4) ≡ -8 ≡ 9
5¹⁴ = 5¹⁰ × 5⁴ ≡ 9 × 13 ≡ 117 ≡ 15 答案：{2, 8, 9, 15}。
(你回头看看，不用去猜什么鬼 gcd，直接一列一筛就出来了！)
实战演练 2：模 41 下，求阶为 8 的所有元素。
已知 6 是模 41 的原根。φ(41) = 40。目标阶 d = 8。
- 步长 S = 40 ÷ 8 = 5。
- 乘数名单（1到8里和8互素的）：1, 3, 5, 7。
- 合格的 k = 1×5=5, 3×5=15, 5×5=25, 7×5=35。
- 终局计算：算 6⁵, 6¹⁵, 6²⁵, 6³⁵ mod 41。
算出来分别是 27, 3, 14, 38。搞定！
五、已知阶，速算大幂
如果你已经知道一个数 a 的阶是 d。那么 aᵈ ≡ 1。 不管头上顶着多大的指数，直接用 d 去除它求余数！
例题：已知 18 模 41 的阶是 5。求 18¹⁸ mod 41。
阶是 5，说明 18⁵ ≡ 1。
把指数 18 拆了：18 ÷ 5 = 3 余 3。
所以 18¹⁸ = (18⁵)³ × 18³ ≡ 1³ × 18³ ≡ 18³ (mod 41)。
直接算 18³ 即可：18² = 324 ≡ 37；18³ ≡ 37 × 18 = 666 ≡ 10。
六、离散对数：单向的密码学神明
- 正向（求幂）：给你 g 和 x，让你算
y = gˣ mod p。这就是普通的模幂运算，用平方表很容易算。 - 反向（离散对数）：告诉你
y = gˣ mod p，已知 y 和 g，让你倒推指数 x 是多少。
结论：反向极度困难！ 只要模数 p 足够大，现在的超级计算机算到宇宙毁灭也算不出 x。 这种“正着容易，倒着难”的特性叫做单向陷门函数。它是整个现代非对称密码学（如 Diffie-Hellman 密钥交换、ElGamal 算法）的基石。期末考概念时只要写出这句话就满分。
🚀 本章做题速查表（考前 5 分钟必看）
| 遇到什么题目 | 应该怎么做 |
|---|---|
| 求某个数的阶 | 先找 φ(m) 的因数！从小到大试这些因数，谁先回到 1 谁就是阶。 |
| 求全部原根 | 已知原根 g，求 gᵏ。k 必须和 φ(m) 互素。 |
| 求指定阶 d 的所有元素 | 用倍数过滤法！ 步长 = φ(m)/d。乘数必须和 d 互素。 |
| 算变态大指数 | 先看底数的阶是不是已知的。如果有阶 d，指数直接对 d 取余数降维！ |
| 问离散对数为什么安全 | 因为“正向求幂容易，逆向求离散对数在计算上不可行”。 |
☠️ 历年期末最惨烈翻车现场
- 错把阶当成 φ(m)：阶是“第一次”出现 1 的指数，它只是 φ(m) 的因数之一，不一定等于 φ(m)。只有原根的阶才等于 φ(m)！
- 求全部原根时，k 的范围找错了：k 是在 1 到 φ(m) 之间找，不是 1 到 m 之间找！比如模 22，是在 1 到 10 里找互素。
- 求指定阶元素，条件用反了：再次默念傻瓜步骤，是“乘数跟目标阶 d 互素”，千万别搞错了。
自测题（没做对别进考场）
- 模 7 的 φ(7) 是多少？2 模 7 的阶可能的值有哪些？
- 已知 2 是模 5 的原根，列出模 5 的全部原根。
- 用“傻瓜三步法”，已知 5 是模 17 的原根（φ(17)=16），列出阶为 4的所有 k 的值（只需写出 k 即可，不用算出最终结果）。
- 已知
ord41(18) = 5，求 18¹² mod 41。
自测答案
- φ(7) = 6。2 的阶可能的值只有 6 的因数：1, 2, 3, 6。（实际算出来是 3）。
- φ(5) = 4。在 1 到 4 里跟 4 互素的是 k=1, 3。所以全部原根是 2¹ 和 2³，即 {2, 3}。
- 目标 d = 4。第一步算步长 S = 16/4 = 4。第二步乘数跟 d(4) 互素：在 1,2,3,4 里跟 4 互素的是 1, 3。第三步合格的 k 为 1×4=4，3×4=12。答案：k = 4, 12。（是不是比硬套公式快多了？）
- 18 的阶是 5，说明每 5 次方就是个 1。指数 12 拆成 10+2。18¹² ≡ 18² = 324 ≡ 37 (mod 41)。