阶与原根

模 $n$ 下和 $n$ 互素的数，乘到某次方总会回到 $1$。欧拉定理保证这件事一定发生，次数是 $\varphi(n)$。真正要问的却是两件更细的事：最小的那个正指数是多少？它能不能刚好等于 $\varphi(n)$？前者叫阶，后者叫原根。有了原根，乘法群就可以用指数来编号，离散对数才说得上话。

阶是什么

设 $n>1$， 是整数且 。满足

的最小正整数 $k$，叫做 $a$ 模 $n$ 的阶，记作 $\mathrm{ord}_n(a)$。

互素是前提。若 $\gcd(a,n)>1$，欧拉定理用不上，$a$ 的幂永远到不了 $1$。例如 $2$ 模 $6$：$2,4,2,4,\ldots$，没有一次同余于 。

$\varphi(n)$ 数的是 $1,2,\ldots,n-1$ 里与 $n$ 互素的个数，也就是乘法群 $(\mathbb{Z}/n\mathbb{Z})^*$ 的阶。欧拉定理说这个群里每个元素满足 ，所以「某次幂回到 」至少发生一次。阶就是其中最小的正指数。

注意「某个幂次等于 $1$」和「最小的那个幂次」不是一回事。前者对所有单位都成立，后者才真正刻画 $a$ 生成了多大的循环。同一个模下，不同的 $a$ 可以有完全不同的阶，只要这些阶都整除 $\varphi(n)$。

阶整除 $\varphi(n)$

先记一条更一般的事实：若 $a^m\equiv 1\pmod n$，则 $\mathrm{ord}_n(a)\mid m$。

证明很短。设 $k=\mathrm{ord}_n(a)$，做带余除法 $m=qk+r$，$0\le r<k$。则

$k$ 已经是最小正指数，所以 $r=0$，即 $k\mid m$。

欧拉定理给出 $a^{\varphi(n)}\equiv 1$，于是立刻得到

这是后面所有算法的底座：不必从 $1$ 试到 $\varphi(n)$，只要在 $\varphi(n)$ 的因子里找。例如模素数 $p$ 时 $\varphi(p)=p-1$，于是每个与 互素的 都满足 ，这比费马小定理 更精细。

再记一条常用推论。若 $\gcd(a,n)=1$，则

特别地，$1,a,a^2,\ldots,a^{k-1}$ 模 $n$ 两两不同。阶为 $k$ 的元素正好生成一个 $k$ 元循环子群。反过来，若已经知道 且 的每个真因子都不满足同余，那个 就是阶。

原根

若 $\mathrm{ord}_n(g)=\varphi(n)$，就称 $g$ 是模 $n$ 的一个原根。

这时 $\{g^0,g^1,\ldots,g^{\varphi(n)-1}\}$ 恰好跑遍全部与 $n$ 互素的剩余类。乘法群 是循环群，生成元就是原根。任意单位 都可以写成 ，指数 在模 下唯一。

不是每个模都有原根。完整条件是：模 $n$ 存在原根，当且仅当

其中 $p$ 是奇素数，$k\ge 1$。于是 $8,15,16,20,21,24$ 这些模都没有原根。$p$ 和 $2p$、以及它们的幂，才是原根真正活跃的地方。

条件里缺掉 $2^k$（$k\ge 3$）不是偶然。模 $2^k$ 时，与 $2$ 互素的奇数都满足 $x^{2^{k-2}}\equiv 1(\mathrm{m}\mathrm{o}$，群的指数严格小于 ，因此生成不了整个单位群。两个不同奇素数的乘积也一样：中国剩余定理把 拆成两个非平凡群的直积，直积不是循环群，原根无从谈起。

一旦原根存在，它们的个数是 $\varphi(\varphi(n))$：从任意一个原根 $g$ 出发，$g^k$ 仍是原根当且仅当 $\gcd(k,\varphi(n))=1$。素数模就是前面的 。

素数模为什么一定有原根

下面只把最常用的情形说清楚：模素数 $p$ 一定存在原根，而且恰好有 $\varphi(p-1)$ 个互不同余的原根。

$\mathbb{F}_p$ 是域，多项式在域上的根不超过次数。设 $d\mid(p-1)$。同余

至多有 $d$ 个解。另一方面，$x^{p-1}-1$ 可以拆成 $(x^d-1)$ 乘上另一个多项式，而费马小定理说每个非零剩余都是 $x^{p-1}-1$ 的根，共 个。所以 恰好有 个根——阶整除 的元素恰好 个。

阶恰好为 $d$ 的个数可以用容斥（或莫比乌斯反演）数出来，结果是 $\varphi(d)$。取 $d=p-1$，原根就有 $\varphi(p-1)$ 个，当然大于 $0$。

也可以构造地看。把 $p-1$ 分解成 $q_1^{a_1}\cdots q_t^{a_t}$。对每个 ，多项式 的根少于 个，所以存在 使

令 $g_i=b_i^{(p-1)/q_i^{a_i}}$，则 。这些阶两两互素，乘积

的阶就是 $p-1$。这就是一个原根。

奇素数幂和 $2p^k$ 的存在性，可以从素数模的原根提升上去：若 $g$ 是模 $p$ 的原根，则 $g$ 与 $g+p$ 中必有一个是模 $p^2$ 的原根，再提升到 。手算和写代码时，知道「先找模 的原根，再对更大的模重新检验」就够用。

怎样检验一个数是不是原根

直接定义要算 $g^1,g^2,\ldots$ 直到 $\varphi(n)$，太慢。因为阶整除 $\varphi(n)$，只需确认 $\varphi(n)$ 的每个真因子都不是阶。再压缩一步：设

则 $g$ 是原根当且仅当对每个素因子 $q_i$，

为什么不必检查 $\varphi(n)$ 的所有真因子？因为若阶是某个真因子 $d$，把 $d$ 的素因子从 $\varphi(n)$ 里剥掉之后，至少会落到某一个 $\varphi(n)/q_i$ 上，从而 。反过来，这 个同余都不成立，阶就不能是任何真因子，只能是 本身。

少检查一个素因子，就可能把阶为 $\varphi(n)/q_i$ 的元素误判成原根。这是最常见的实现错误。

找原根的实用策略：从 $2,3,5,\ldots$ 依次试，用上面的判别。素数模上原根的密度大约是 $\varphi(p-1)/(p-1)$，通常很快就能碰到。不必先手写存在性证明再枚举——对 $8$ 这类没有原根的模，枚举到头会失败，代码里应先用存在条件拦住，避免把「找不到」和「程序写错」混在一起。

若只要阶而不是原根，算法几乎一样：从 $\varphi(n)$ 出发，对每个素因子 $q$ 能除就除，直到 $a^{o/q}\not\equiv 1$。最后剩下的 $o$ 就是阶。这个过程不会漏掉因子，因为阶的素因子只能来自 。

手算例子

例一：算出阶

求 $2$ 模 $7$ 的阶。$\varphi(7)=6$，正因子是 $1,2,3,6$。

所以 $\mathrm{ord}_7(2)=3$，不是原根。$3$ 整除 $6$，符合定理。

再看 $3$ 模 $7$：

$3^{6/2}=3^3\not\equiv 1$，$3^{6/3}=3^2\not\equiv 1$，所以 是原根。模 的原根应有 个。一般地，若 是原根，则 仍是原根当且仅当 ：因为 ，要让右边仍等于 ，分子分母必须互素。这里另一个是 。、、 的阶分别是 ，都不是原根。

例二：用素因子检验

判断 $2$ 是不是模 $13$ 的原根。$\varphi(13)=12=2^2\cdot 3$，要检查的指数是 $12/2=6$ 和 。

两个都不是 $1$，所以 $2$ 是原根。幂次列出来也能对上：$1,2,4,8,3,6,12,11,9,5,10,7$，到第 $12$ 项才回到 ，且中间没有重复。于是每个与 互素的剩余——也就是 到 ——都能写成 的幂。

例三：没有原根的模

模 $8$ 与 $8$ 互素的剩余类只有 $1,3,5,7$，都满足 $x^2\equiv 1\pmod 8$。，但没有任何元素的阶达到 。这就是 落在存在性条件外面的具体样子。

模 $15$ 同样没有原根：$\varphi(15)=8$，单位是 $1,2,4,7,8,11,13,14$。直接算幂，$2^4=16\equiv 1$，，，。每个单位都满足 ，群的指数是 而不是 ，生成不了整个 。

例四：手算一个离散对数

已知 $2$ 是模 $13$ 的原根，求 $\log_2 10$，也就是满足 $2^k\equiv 10\pmod{13}$ 的 。接着例二的幂表往下乘：

所以 $\log_2 10=10$。指数把乘法变成加法时，底数的幂在模 $13$ 下算，指数本身要模 $\varphi(13)=12$。例如 $10\cdot 8\equiv 80\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}13)$，而 ，右边正好是 。把这两个模弄反，验算会对不上。

指数与离散对数

固定一个原根 $g$。对每个与 $n$ 互素的 $a$，存在唯一的 $k\in\{0,1,\ldots,\varphi(n)-1\}$ 使

这个 $k$ 叫做 $a$ 以 $g$ 为底、模 $n$ 的指数或离散对数，记作 $\mathrm{ind}_g a$ 或 $\log_g a$。

指数把乘法变成加法：

高次同余 $x^k\equiv a\pmod p$ 也可以先取指数，变成一次同余 $k\cdot\mathrm{ind}\,x\equiv\mathrm{ind}\,a\pmod{p-1}$。有没有解，回到上一篇的判别： 能否整除右边。解的个数也是那个最大公因子。例如模 解 。，方程变成 ， 整除 ，有三个解 ，对应 。验算：，，。

求离散对数没有一般的多项式时间算法。模不太大时，小步大步（baby-step giant-step）就能用。令 $m=\lceil\sqrt{\varphi(n)}\rceil$，写 $k=im+j$，其中 。先把 存进哈希表（小步），再枚举 去查（大步）。时间、空间都是 。它是入门算法，不是密码学里的最优攻击；更大的模需要更专门的方法。

一份可直接用的实现

下面给出：欧拉函数、阶、原根检验、找最小正原根，以及素数模上的 BSGS 离散对数。找原根前需要 $\varphi(n)$ 的素因子，这里用试除分解，对竞赛和手算规模足够。

order 从 $\varphi(n)$ 往下剥素因子，复杂度主要是分解加上几次快速幂。discrete_log 用费马小定理取逆，只适用于素数模；一般模要把步长改成 $\lceil\sqrt{\varphi(n)}\rceil$，并保证 $g$ 真是原根，或至少生成了 。

跑一下应对上前面的手算：$2$ 模 $7$ 阶为 $3$，$3$ 模 $7$ 是原根，$2$ 模 $13$ 是原根，$2^4\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}13)$。模 没有原根，函数返回 ，和存在性条件一致。

写代码时容易踩的坑

先确认 $\gcd(g,n)=1$。不对互素做检查，$g^{\varphi(n)}\bmod n$ 可能根本不是 $1$，后面的判别全部失真。

$g^{\varphi(n)}\equiv 1$ 不能说明 $g$ 是原根。欧拉定理对所有单位都成立。必须对 $\varphi(n)$ 的每个素因子做 $g^{\varphi(n)/q}\not\equiv 1$。

$\varphi(n)$ 的素因子不能漏。$p-1=12=2^2\cdot 3$，只检查 $2^6$ 而漏掉 ，会把阶为 的元素当成原根。分解的是 ，不是 。

最小原根不一定是 $2$。$2$ 模 $7$ 就不是。从 $2$ 开始枚举没问题，但不要写死「先试 $2$ 并假设成功」。

模 $p^k$ 时，模 $p$ 的原根未必仍是模 $p^2$ 的原根。提升之前要用 $g^{p-1}\not\equiv 1\pmod{p^2}$ 再验一次，或者直接对 跑完整的素因子判别。

离散对数的答案在模 $\mathrm{ord}(g)$ 下才唯一。BSGS 的表项冲突时要核对 $g^k\equiv a$，不要看见哈希命中就返回。$a\equiv 0$ 在素数模上没有对数，应单独拒绝。

Python 的 pow(a, e, m) 已经是快速幂，不必自己写二进制展开；但 $e$ 为负时它要求 $a$ 可逆。素数模用费马、$a^{p-2}$ 即可，一般模请回到扩展欧几里得。

不要把加法群的生成元和乘法群的原根混为一谈。$1$ 永远生成 $(\mathbb{Z}/n\mathbb{Z},+)$，但 $1$ 的乘法阶是 $1$，只有 $n=2$ 时才是原根。讨论原根时，始终站在「与 $n$ 互素的那些剩余、做乘法」这一边。

它连着什么

原根把「模 $p$ 乘法」翻译成「模 $p-1$ 加法」。Diffie–Hellman 一类协议的硬度叙述，都建立在离散对数难算上；一次同余、中国剩余定理、原根检验则是这些实现里最底层的几块砖。

更高次同余 $x^k\equiv a\pmod p$ 有解的一个判别是 $a^{(p-1)/\gcd(k,p-1)}\equiv 1$，证明就是两边取指数。阶与原根不是竞赛里的偏题，而是把循环群真正用起来的那一层语言。把定义、整除关系和检验三个素因子条件分开，手算和代码就会对得上。下一步若要解二次同余，可以先问原根存在与否；若只要判断「是不是生成元」，按本文的素因子检验写就行，不必再从一次方慢慢乘到 。这一层写对了，后面的指数运算才站得住。