★ FEATURED ARTICLE 1. 原根到底是什么从一个“能生成一切”的数说起1.1 先看一个现象模 7 下的幂次循环学数论的人第一次接触原根多半是从一张“幂次余数表”开始的。我们看模 7 的情况取底数 3把它的各次幂写出来3^1 3模 7 余 33^2 9模 7 余 23^3 27模 7 余 63^4 81模 7 余 43^5 243模 7 余 53^6 729模 7 余 1注意到一个惊人的事实从 3 出发连续取幂再取模得到的余数是 3、2、6、4、5、1刚好把模 7 下所有非零余数 1 到 6 全部走了一遍一个不多一个不少然后回到 1开始新一轮循环。这个“走遍全场”的性质就是原根的本质。更正式地说如果模 m 下的乘法群存在一个元素 g使得 g 的幂次能够生成群中的所有元素那么 g 就是模 m 的原根也就是这个循环群的生成元。群论里叫做 cyclic group generator数论里则直接叫 primitive root modulo m。1.2 阶order与原根的严格定义要真正理解原根必须先弄明白“阶”的概念。给定一个与模数 m 互素的整数 a我们把满足 a^k ≡ 1 (mod m) 的最小正整数 k 称为 a 模 m 的阶记作 ord_m(a)。举个例子模 7 下2^1 ≡ 22^2 ≡ 42^3 ≡ 8 ≡ 1所以 2 模 7 的阶是 3。而 3^1 ≡ 33^2 ≡ 23^3 ≡ 63^4 ≡ 43^5 ≡ 53^6 ≡ 1所以 3 模 7 的阶是 6。这里的 6 恰好等于 φ(7) 6。φ 是欧拉函数表示小于 m 且与 m 互素的数有多少个。当某个数 a 的阶恰好等于 φ(m) 时这个 a 就是模 m 的原根。换句话说原根就是达到“最大可能阶”的那个元素。用生活化的类比理解一群广场舞成员围成圈每个人按固定步长跳一步。正常人的步长可能在跳几步之后就回到原点但“原根”这个人很特别他必须走满 φ(m) 步才能回到原点而在这 φ(m) 步里他踩过了圈上每一个位置。这个类比很贴近原根在群论里的含义——生成整个循环群的生成元。提示阶的定义要求 gcd(a, m) 1否则 a 的幂次永远不可能回到 1因为一旦某个质因子和 m 共享余数序列会退化到某个约数环里根本没法讨论“循环”这件事。1.3 为什么计算机和密码学都离不开原根原根这些年受到的关注越来越多不是因为它是个优美的数学概念而是因为它实打实地用在密码学里。最直接的应用就是离散对数问题给定一个大素数 p 和它的原根 g任取一个非零余数 a找唯一存在的整数 x 使得 g^x ≡ a (mod p)这个 x 就是离散对数。如果 p 取一个 2048 位的大素数那么已知 g 和 a 合法算出 x 非常困难这个“正着算容易、反着算难死”的性质构成了 Diffie-Hellman 密钥交换、ElGamal 加密方案、数字签名等一系列现代密码协议的基础。换句话说原根不是纸面上的奇技淫巧而是信息安全的底层砖石。谁适合认真学这块内容我认为三类人最值得花时间一是正在学初等数论和抽象代数的学生原根是沟通两个领域的最佳桥梁二是做密码学工程的同学理解原根能让你明白自己用的协议参数为什么这样设计三是打算法竞赛的程序员找原根是一类经典数论题相关模板代码应该烂熟于心。2. 什么样的模数才有原根存在性定理与判定方法2.1 不是所有模数都能“生成全场”很多人初学原根时会想当然地认为“每个模数都有原根”这个直觉是错的。比如模 8和它互素的数有哪些1、3、5、7一共 4 个所以 φ(8) 4。但是我们实际算一下会发现3^2 ≡ 9 ≡ 1 (mod 8)5^2 ≡ 25 ≡ 1 (mod 8)7^2 ≡ 49 ≡ 1 (mod 8)最大可能阶只有 2。也就是说模 8 的乘法群连一个阶为 4 的元素都找不到更不可能有原根。标准结论长这样模 m 存在原根当且仅当 m 1、2、4、p^k 或 2p^k这里 p 是奇素数k 是正整数。除此之外比如 m 含有两个不同的奇素因子或者 m 是 8 的倍数统统没有原根。这个定理在实操中非常有用。比如你在设计一个密码算法模数选的是一个大素数 p那一定存在原根放心去求即可。但如果你的参数里有类似 153×5这样的数直接放弃寻找原根因为没有就是没有再怎么枚举也是白费力气。2.2 为什么模 2、4 和奇素数幂会特殊很多初学者会问为什么偏偏是 1、2、4、p^k、2p^k 这几种形式呢背后的核心原因是这些模数对应的乘法群是循环群群论里已经证明这类群的阶结构足够“均匀”能满足一个元素走遍全场的条件。以 p^k 为例数学上的证明是从原根的存在性出发用 Hensel 引理把模 p 的原根“提升”到模 p^k 的原根。这个过程简单说就是先在模 p 的小世界里找到一个生成元然后通过逐步修正让它适配模 p^2、p^3 直到 p^k 的大世界。每一步修正只需要检查少量条件总能成功。2p^k 的情形更简单因为在奇素数幂的情况下模 2p^k 的乘法群实际上和模 p^k 的乘法群同构。直观来说一个偶数模数只是在原有结构上平添了一个无关紧要的 2 因子群的循环性质没有被破坏。同理p^k 和 p^l 在 k 和 l 不同时的“规模”不同但循环性是保持的。注意这里说“模 p^k 一定有原根”时默认 p 是奇素数。模 2^kk ≥ 3是没有原根的原因就在 2.1 里已经看到了——阶的值被压得很低永远到不了 φ(2^k) 2^{k-1}。2.3 原根的数量φ(φ(m)) 个生成元假设模 m 存在原根那到底有几个原根答案不是 1 个而是一大堆。如果 g 是一个原根那么所有 g^k 中只要 gcd(k, φ(m)) 1g^k 也一定是原根。原因很简单幂次的阶是 φ(m)/gcd(k, φ(m))要让阶保持为 φ(m)就必须让 gcd(k, φ(m)) 1。所以原根的数量等于 φ(φ(m))。举两个实例算一遍。模 7 下φ(7) 6原根数量为 φ(6) 2而 3 和 5 确实就是那两个原根。模 31 下φ(31) 30原根数量为 φ(30) 8算上枚举验证原根分别是 3、11、12、13、17、21、22、24 这 8 个一个不多一个不少。这个数量规律在竞赛和密码学选参数时很实用。你随机取一个与模数互素的数它恰好是原根的概率大约是 φ(φ(m)) / φ(m)。当 m 是一个大素数 p 时这个比例约为 φ(p-1)/(p-1)一般来说并不算特别低随机试几次就能命中。这为后续“快速找一个原根”提供了概率依据。3. 手把手找原根判断逻辑、筛法与代码实现3.1 用“约数排除法”快速判定原根最粗暴的找原根方法就是枚举 g 2, 3, 4, ...对每个 g 计算它模 m 的阶看是否等于 φ(m)。但问题在于直接算阶需要枚举 k 1 到 φ(m)然后检查 g^k mod m 是否等于 1当 φ(m) 很大时这种做法毫无可行性。真正高效的判定逻辑是利用阶整除 φ(m) 这一事实只需要检查 φ(m) 的每个质因子 p_i看 g^(φ(m)/p_i) mod m 是否等于 1。只要有一个质因子让结果等于 1说明 g 的阶严格小于 φ(m)g 就不是原根如果对每个质因子结果都不等于 1则 g 一定是原根。这个做法的原理是阶一定整除 φ(m)而且阶小于 φ(m) 当且仅当阶是 φ(m) 除以某个质因子后的约数。换句话说如果 g 的真阶存在它必然暴露在某个“φ(m)/p_i”的检查中。把检查次数从 φ(m) 降到了 φ(m) 的质因子个数通常是个位数。我习惯把这个过程叫作“约数排除法”理由很形象我们不看完整阶而是看“砍掉一个质因子”之后是否提前回到了 1。提前回到 1 就说明阶不够大直接淘汰。3.2 实操流程求模 31 的一个原根我们以模 31 为例走一遍完整流程。首先计算 φ(31) 30分解质因数得 30 2 × 3 × 5。要检查的指数是 30/2 15、30/3 10、30/5 6。下面从 g 2 开始试g 2计算 2^15 mod 31 1直接淘汰因为这说明 2 的阶整除 15达不到 30。g 3依次计算 3^6 mod 31 163^10 mod 31 253^15 mod 31 30三个结果都不等于 1所以 3 是模 31 的原根。一次就命中了。实际中如果第一个候选被淘汰就换下一个继续验证由于原根密度不算低通常试个几次就会成功。用大素数 p 时情况也类似候选从 2 开始往上枚举即可实战中很少需要枚举超过 10 个候选。3.3 完整 Python 代码找任意模数的原根代码实现其实不复杂拆成几个函数即可线性筛素数、欧拉函数、质因数分解、快速幂取模、原根判定。下面是一份经过我多次使用的模板大家可以直接抄作业import math def get_primes_upto(n): 线性筛法返回 [2, n] 的所有素数列表 is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) for p in primes: if i * p n: break is_prime[i * p] False if i % p 0: break return primes def euler_phi_single(x): 对单个 x 求欧拉函数 φ(x) result x t x p 2 while p * p t: if t % p 0: result result // p * (p - 1) while t % p 0: t // p p 1 if p 2 else 2 if t 1: result result // t * (t - 1) return result def factorize(x): 对 x 分解质因数返回质因子列表去重 factors [] p 2 while p * p x: if x % p 0: factors.append(p) while x % p 0: x // p p 1 if p 2 else 2 if x 1: factors.append(x) return factors def mod_pow(a, b, m): 快速幂取模 a^b mod m result 1 base a % m while b 0: if b 1: result result * base % m base base * base % m b 1 return result def is_primitive_root(g, m, phi, factors): 判定 g 是否是模 m 的原根需传入 φ(m) 和它的质因子列表 if math.gcd(g, m) ! 1: return False for p in factors: if mod_pow(g, phi // p, m) 1: return False return True def find_primitive_root(m): 找到一个模 m 的原根找不到返回 -1 if m 1: return 0 phi euler_phi_single(m) factors factorize(phi) for g in range(2, m): if is_primitive_root(g, m, phi, factors): return g return -1 # 示例 for m in [7, 8, 15, 31, 97, 119]: g find_primitive_root(m) print(fm{m}, phi{euler_phi_single(m)}, 原根{g})跑一下这段代码输出结果会非常直观模 7 返回 3模 8 返回 -1模 15 返回 -1模 31 返回 3模 97 返回 5模 119 返回 -1。这个结果和 2.1 里的存在性定理完全一致说明代码逻辑和数学理论互相印证了。3.4 大模数场景的工程优化心得上面这份代码在 m 超过 10^9 时会遇到瓶颈主要体现在两个地方。一是快速幂取模本身没问题但质因数分解的试除算法效率太低建议提前筛好 10^6 以内的素数表只拿素数去试除这样轻松支持到 64 位整数范围内的分解。二是在需要大量重复计算 φ(m) 时建议预处理欧拉函数表把复杂度从 O(√m) 降到 O(N log log N)。如果模数是密码学场景下的 2048 位大素数上述算法全部失效需要用更高级的工具比如 Borwein 的算法或专用数论库中的函数。但在教学和竞赛层面上面的模板已经覆盖了绝大多数需求。注意在大素数 p 下求原根时很多人会直接枚举 g 2, 3, 5, 7 等小素数。小素数天然和 p 互素省去了 gcd 检查同时命中率不低。这是一个非常实用的细节但要注意不能因此跳过质因子分解步骤因为判定原根依然需要所有 φ(m) 的质因子。4. 从数学到密码学原根在现代加密体系中的实战位置4.1 离散对数原根带来的“单向门”在了解原根的概念后一个自然的问题是为什么密码学偏偏看重原根而不是随便找一个普通元素答案在于离散对数问题Discrete Logarithm Problem, DLP的安全性需要依赖原根生成的群结构。想象一个场景选择一个大素数 p 97原根 g 5。我们随机生成一个私钥 x 33算公钥 y 5^33 mod 97。正向计算这个过程是秒级的任何人都能轻松完成。但是反过来如果只告诉你 y 58要你在有限时间内求出 x 33除了暴力枚举所有从 1 到 96 的 x 并逐一验证之外没有有效的通用方法。当 p 扩展到大素数级别时暴力枚举就完全不可能了。这里的本质是原根 g 的幂次能把离散空间中的每个元素都映射成 g 的某个指数但指数和底数之间的对应关系就像把一杯水倒进大海找出是哪一滴水倒进去的极其困难。生活化地说原根是一个“单向门的钥匙”推门进去容易逆着走出来几乎不可能。4.2 经典协议拆解Diffie-Hellman 密钥交换Diffie-Hellman 协议简称 DH是原根在密码学中最经典的应用之一它解决的问题是两个人在公开信道上交换信息如何让彼此最终共享同一个密钥同时保证第三方无法算出这个密钥。假设通信双方使用共享参数大素数 p 和它的原根 g这两个值公开。A 随机选择私钥 a计算 A g^a mod p发送 A 给对方。B 随机选择私钥 b计算 B g^b mod p发送 B 给对方。随后 A 用收到的 B 计算密钥 K B^a mod p g^{ab} mod pB 用收到的 A 计算密钥 K A^b mod p g^{ab} mod p。两个人最终得到了一样的 K而窃听者只看到了公开的 p、g、A、B要破解 K 就必须从 A 和 B 中反推出 a 或 b这就落在离散对数问题的难度上。这里的 p 和 g 不是随便选的。p 必须是一个“安全素数”通常要求 p 2q 1 且 q 也是素数这样 p-1 的大质因子 q 能在很大程度避免群结构被攻击。而 g 的选择也很讲究有些实现直接取 g 2方便运算但为了安全性更高有时会选择一个阶为 q 的生成元而非阶为 p-1 的完整原根。这些细节都是在真实工程中反复权衡之后的经验沉淀。提示并非所有密码学场景都需要完整的原根。在构建某些群时我们希望群有一个“大素数阶子群”这时只需要找一个元素其阶等于大素数因子 q不需要它生成整个循环群。这点常常被初学者混淆值得特别留意。4.3 再往下走ElGamal、伪随机数与原根的延伸价值除了 DH 协议ElGamal 加密方案同样依赖原根。它的加密过程是接收方公开大素数 p、原根 g 和公钥 y g^x mod p发送方选随机数 k计算 c1 g^k mod p 和 c2 m * y^k mod p然后把 (c1, c2) 发给接收方。接收方用私钥 x 计算 c2 * c1^{-x} mod p恰好还原出明文 m。整个过程安全性的根基依然是离散对数的困难度。原根在非密码学领域也有应用。比如线性同余伪随机数生成器在某些设计下会用原根来保证周期的最大化用原根取幂的序列天然具备均匀分布的统计性质。在竞赛中原根还常被用来构造“原根表”进而快速求解离散对数配合大步小步算法Baby-step Giant-step能在 √p 时间复杂度内算完中等规模的离散对数。我对原根最深的感触是它像一个枢纽把初等数论、抽象代数、计算复杂度和工程安全四块知识串成了环。学起来看似只是一条定理几个例子真正进入应用层面时才发现每个环节都离不开它的支撑。5. 常见误区、排查技巧与我的实操心得5.1 四个最容易踩的坑第一个坑认为所有奇数模数都有原根。模 15 就是反例φ(15) 8但实际枚举会发现没有任何一个数的阶能达到 8因为 15 不是一个奇素数的幂。以后看到合数模数不要再盲目去找原根了先判断 m 的形式是否满足条件。第二个坑只检查部分质因子就下结论。有些人图省事只验证一个或两个 φ(m) 的质因子比如只检查 g^(φ(m)/2) 和 g^(φ(m)/3)漏掉最大质因子。这会导致把非原根误判为原根后续算出的离散对数可能就是错的。我的建议是质因子列表必须完整一个不能漏。第三个坑混淆原根和阶。原根要求阶等于 φ(m)但有时候某个元素的阶恰好等于一个较大的质因子比如 p 23φ(23) 22 2 × 115 的阶可能是 11 而不是 22。这种元素在密码学中也很有价值但它不是原根使用时必须分清楚。第四个坑代码里对 m 1 或 m 2 的边界处理不当。φ(1) 定义为 1但找原根的过程在模 1 下是平凡情况很多模板会越界或死循环。工程上建议对 m 1 直接返回 0 或做特殊标记。5.2 排查实录一次找原根找错的经验有一次我需要给一个大模数找原根用的是自己手写的模板结果找到的“原根”在后续离散对数计算中反复出错。排查了一下才发现问题出在质因数分解函数在碰到完全平方数的质因子时没有把重复因子除尽导致质因子列表多了一个本应合并的小因子。比如把 12 分解成 [2, 2, 3] 和 [2, 3] 在数学上是等价的但对判定步骤来说多出来的重复因子会让检查次数变多却不会影响正确性。我当时真正的问题其实是 φ(m) 算错了少算了一个因子导致检查指数不完整误把一个阶较小的元素当成了原根。这类问题最隐蔽因为逻辑代码看起来都对单纯结果不对。我的经验是在任何找原根的流程中先单独验证 φ(m) 是否算对再验证质因子分解是否完整最后再枚举候选 g。每一步都自己手动用一个小模数验证一遍能省去后面排查半天的时间。另一个值得记录的经验是当 φ(m) 非常大时不要一次性把所有 g 的幂次都算出来应该计算一个缓存表把 g、g^2、g^4、g^8 等按平方递增的方式存下来每个候选 g 都复用同一套幂表。这样在连续测试多个候选 g 时能节省大量计算。尤其当 m 是一亿级别的数时这个技巧能明显缩短耗时。5.3 一张速查表帮你少翻书模数φ(m)是否存在原根原根示例备注21是1平凡情况32是2素数42是32 的平方54是2, 3素数76是3, 5素数84否-2 的立方无原根96是2, 53 的平方158否-两个奇素因子1918是2, 3素数3130是3, 11, 12, 13, 17, 21, 22, 24素数这张表建议自己也可以多生成几组做成随手的参考因为原根计算一旦进入实际应用往往需要快速判断而不想每次都从定义出发。5.4 我的三条实操建议第一从 2 开始枚举候选 g 几乎总是最优解。因为 2 是大于 1 的最小整数计算最方便而且很多模数的原根恰好就是 2比如模 19、模 29、模 47。即使 2 不是原根多半也只是被其中一两个质因子淘汰测试代价很小。第二如果你在做竞赛题建议把原根查找模块封装成函数并一次写好之后所有涉及离散对数的题目都能直接调用。这个模块不依赖任何第三方库只用标准库 math也许 60 行代码值得反复测试到烂熟。第三生产环境一定要加日志记录候选项和被淘汰的原因。很多时候你以为找到了一个原根实际只是漏检了一个质因子日志能帮你在对账时立刻定位是哪个候选、哪个因子出了问题。把原根这一块啃明白之后再回头读密码学论文、看参数生成代码、理解离散对数攻击手段都会觉得豁然开朗。我自己的体会是这个知识点值得花几天时间彻底吃透因为它值得的成本会在后续所有相关领域里成倍地收回。
阅读完成 · 觉得有帮助？
