原根

前置知识：费马小定理，欧拉定理，拉格朗日定理。

阶和原根是定义 离散对数 的关键工具。其在抽象代数中的推广可参见 群论 和 环论 的相关章节。

阶

性质 1

$a,a^2,\cdots ,a^{{\delta }_m(a)}$ 模 $m$ 两两不同余。

性质 2

若 $a^n\equiv 1(\mathrm{mod}m)$，则 ${\delta }_m(a)\mid n$.

证明

对 $n$ 除以 ${\delta }_m(a)$ 作带余除法，设 $n={\delta }_m(a)q+r,0\le r<{\delta }_m(a)$.

若 $r>0$，则

$$a^r\equiv a^r(a^{{\delta }_m(a)}{)}^q\equiv a^n\equiv 1(\mathrm{mod}m)$$

这与 ${\delta }_m(a)$ 的最小性矛盾。故 $r=0$，即 ${\delta }_m(a)\mid n$.

据此还可推出：

若 $a^p\equiv a^q(\mathrm{mod}m)$，则有 $p\equiv q(\mathrm{mod}{\delta }_m(a))$.

还有两个与四则运算有关的重要性质。

性质 3

设 $m\in {\mathbf{N}}^{\ast }$，$a,b\in \mathbf{Z}$，$(a,m)=(b,m)=1$，则

$${\delta }_m(ab)={\delta }_m(a){\delta }_m(b)$$

的充分必要条件是

$$({\delta }_m(a),{\delta }_m(b))=1$$

性质 4

设 $k\in \mathbf{N}$，$m\in {\mathbf{N}}^{\ast }$，$a\in \mathbf{Z}$，$(a,m)=1$，则

$${\delta }_m(a^k)={\displaystyle \frac{{\delta }_m(a)}{({\delta }_m(a),k)}}$$

证明

注意到：

$$\begin{array}{rl}& a^{k{\delta }_m(a^k)}=(a^k{)}^{{\delta }_m(a^k)}\equiv 1(\mathrm{mod}m)\\ ⟹& {\delta }_m(a)\mid k{\delta }_m(a^k)\\ ⟹& {\displaystyle \frac{{\delta }_m(a)}{({\delta }_m(a),k)}}\mid {\delta }_m(a^k)\end{array}$$

另一方面，由 $a^{{\delta }_m(a)}\equiv 1(\mathrm{mod}m)$，可知：

$$(a^k{)}^{\frac{{\delta }_m(a)}{({\delta }_m(a),k)}}=(a^{{\delta }_m(a)}{)}^{\frac{k}{({\delta }_m(a),k)}}\equiv 1(\mathrm{mod}m)$$

故：

$${\delta }_m(a^k)\mid {\displaystyle \frac{{\delta }_m(a)}{({\delta }_m(a),k)}}$$

综合以上两点，得：

$${\delta }_m(a^k)={\displaystyle \frac{{\delta }_m(a)}{({\delta }_m(a),k)}}$$

原根

若一个数 $m$ 有原根 $g$，则 $g,g^2,\dots ,g^{\phi (m)}$ 构成模 $m$ 的简化剩余系。

特别地，当 $m$ 是质数时，有 $g^{i}modm$，$0<i<m$ 的结果两两不同。

原根判定定理

设 $m⩾3,(g,m)=1$，则 $g$ 是模 $m$ 的原根的充要条件是，对于 $\phi (m)$ 的每个素因数 $p$，都有 $g^{\frac{\phi (m)}{p}}\not\equiv 1(\mathrm{mod}m)$.

原根个数

若一个数 $m$ 有原根 $g$，那么对于任意 $\phi (m)$ 的因子 $d$，模 $m$ 的 $d$ 阶元素存在且个数为 $\phi (d)$。

特别地，$m$ 的原根个数为 $\phi (\phi (m))$。

原根存在定理

我们来证明它，分成 $m=2,4$、$m=p^{\alpha }$、$m=2p^{\alpha }$ 与 $m\ne 2,4,p^{\alpha },2p^{\alpha }$，四个部分。

1. $m=2,4$，原根显然存在。

2. $m=p^{\alpha }$，其中 $p$ 为奇素数，$\alpha \in {\mathbf{N}}^{\ast }$.

   定理 1

   对于奇素数 $p$，$p$ 有原根。

   证明

   先证一个引理：

   设 $a$ 与 $b$ 是与 $p$ 互素的两个整数，则存在 $c\in \mathbf{Z}$ 使得 ${\delta }_p(c)=[{\delta }_p(a),{\delta }_p(b)]$.

   证明

   我们先将 ${\delta }_m(a),{\delta }_m(b)$ 表示成质因数分解的形式：

   $$({\delta }_m(a)=\prod _{i=1}^k{p}_i^{{\alpha }_i},{\delta }_m(b)=\prod _{i=1}^k{p}_i^{{\beta }_i})$$

   接着将它们表示成如下形式：

   $${\delta }_m(a)=XY,{\delta }_m(b)=ZW$$

   其中：

   • $Y=\prod _{i=1}^k{p}_i^{[{\alpha }_i>{\beta }_i]{\alpha }_i}$
   • $X={\displaystyle \frac{{\delta }_m(a)}{Y}}$
   • $W=\prod _{i=1}^k{p}_i^{[{\alpha }_i\le {\beta }_i]{\beta }_i}$
   • $Z={\displaystyle \frac{{\delta }_m(b)}{W}}$

   则由阶的 性质 4，可得：

   $$\begin{array}{rl}{\delta }_m\left(a^X\right)& ={\displaystyle \frac{{\delta }_m(a)}{({\delta }_m(a),X)}}\\ & ={\displaystyle \frac{XY}{X}}\\ & =Y\end{array}$$

   同理：

   $${\delta }_m\left(b^Z\right)=W$$

   又因为显然有 $(Y,W)=1$，$YW=[{\delta }_p(a),{\delta }_p(b)]$，则再由阶的 性质 3，可得：

   $$\begin{array}{rl}{\delta }_m\left(a^X{b}^Z\right)& ={\delta }_m\left(a^X\right){\delta }_m\left(b^Z\right)\\ & =YW\\ & =[{\delta }_p(a),{\delta }_p(b)]\end{array}$$

   于是令 $c=a^X{b}^Z$ 则原命题得证。

   回到原命题，对 $1\sim (p-1)$ 依次两两使用引理，可知存在 $g\in \mathbf{Z}$ 使得

   $${\delta }_p(g)=[{\delta }_p(1),{\delta }_p(2),\cdots ,{\delta }_p(p-1)]$$

   这表明 ${\delta }_p(j)\mid {\delta }_p(g)(j=1,2,\cdots ,p-1)$，所以 $j=1,2,\cdots ,p-1$ 都是同余方程

   $$x^{{\delta }_p(g)}\equiv 1(\mathrm{mod}p)$$

   的根。由拉格朗日定理，可知方程的次数 ${\delta }_p(g)\ge p-1$.

   又由费马小定理，易知 ${\delta }_p(g)\le p-1$，故 ${\delta }_p(g)=p-1=\phi (p)$.

   综上可知 $g$ 为模 $p$ 的原根。

   定理 2

   对于奇素数 $p$，$\alpha \in {\mathbf{N}}^{\ast }$，$p^{\alpha }$ 有原根。

   证明

   一个基本的想法是将模 $p$ 的原根平移。

   先证明一个引理：

   存在模 $p$ 的原根 $g$，使得 $g^{p-1}\not\equiv 1(\mathrm{mod}{p}^2)$.

   证明

   事实上，任取模 $p$ 的原根 $g$，若 $g$ 不满足条件，我们认定 $g+p$ 满足条件。

   易知 $g+p$ 也是模 $p$ 的原根。

   我们有

   $$\begin{array}{rl}(g+p{)}^{p-1}& \equiv (\genfrac{}{}{0ex}{}{p-1}{0})g^{p-1}+(\genfrac{}{}{0ex}{}{p-1}{1})p{g}^{p-2}(\mathrm{mod}{p}^2)\\ & \equiv g^{p-1}+p(p-1)g^{p-2}(\mathrm{mod}{p}^2)\\ & \equiv 1-p{g}^{p-2}(\mathrm{mod}{p}^2)\\ & \not\equiv 1(\mathrm{mod}{p}^2)\end{array}$$

   回到原题，我们证明若 $g$ 是一个满足引理条件的原根，则对任意 $\alpha \in {\mathbf{N}}^{\ast }$，$g$ 是模 $p^{\alpha }$ 的原根。

   首先，证明下面的结论：对任意 $\beta \in {\mathbf{N}}^{\ast }$，都可设

   $$g^{\phi (p^{\beta })}=1+p^{\beta }{k}_{\beta }$$

   这里 $p\nmid k_{\beta }$。事实上，$\beta =1$ 时，由 $g$ 的选取可知结论成立。现设上式对 $\beta$ 时成立，则

   $$\begin{array}{rl}{g}^{\phi (p^{\beta +1})}& ={\left(g^{\phi \left(p^{\beta }\right)}\right)}^p\\ & ={(1+p^{\beta }{k}_{\beta })}^p\\ & \equiv 1+p^{\beta +1}{k}_{\beta }(\mathrm{mod}{p}^{\beta +2})\end{array}$$

   结合 $p\nmid k_{\beta }$ 可知命题对 $\beta +1$ 成立。

   所以命题对任意 $\beta \in {\mathbf{N}}^{\ast }$ 都成立。

   其次，记 $\delta ={\delta }_{p^{\alpha }}(g)$，则由欧拉定理，可知 $\delta \mid p^{\alpha -1}(p-1)$.

   而由 $g$ 为模 $p$ 的原根，及 $g^{\delta }\equiv 1(\mathrm{mod}{p}^{\alpha })$.

   所以可设 $\delta =p^{\beta -1}(p-1)$，这里 $1\le \beta \le \alpha$.

   现在利用之前的结论，可知：

   $$g^{\phi (p^{\beta })}\not\equiv 1(\mathrm{mod}{p}^{\beta +1})⟹g^{\delta }\not\equiv 1(\mathrm{mod}{p}^{\beta +1})$$

   结合 $g^{\delta }\equiv 1(\mathrm{mod}{p}^{\alpha })$ 可知 $\beta \ge \alpha$.

   综上可知，$\beta =\alpha$，即：

   $${\delta }_{p^{\alpha }}(g)=p^{\alpha -1}(p-1)=\phi (p^{\alpha })$$

   从而，$g$ 是模 $p^{\alpha }$ 的原根。

3. $m=2p^{\alpha }$，其中 $p$ 为奇素数，$\alpha \in {\mathbf{N}}^{\ast }$.

   定理 3

   对于奇素数 $p$，$\alpha \in {\mathbf{N}}^{\ast }$，$2p^{\alpha }$ 的原根存在。

   证明

   设 $g$ 是模 $p^{\alpha }$ 的原根，则 $g+p^{\alpha }$ 也是模 $p^{\alpha }$ 的原根。

   在 $g$ 和 $g+p^{\alpha }$ 中有一个是奇数，设这个奇数是 $G$，则 $(G,2p^{\alpha })=1$.

   由欧拉定理，${\delta }_{2p^{\alpha }}(G)\mid \phi (2p^{\alpha })$.

   而 $G^{{\delta }_{2p^{\alpha }}(G)}\equiv 1(\mathrm{mod}2p^{\alpha })$，故：

   $$G^{{\delta }_{2p^{\alpha }}(G)}\equiv 1(\mathrm{mod}{p}^{\alpha })$$

   利用 $G$ 为模 $p^{\alpha }$ 的原根可知 $\phi (p^{\alpha })\mid {\delta }_{2p^{\alpha }}(G)$.

   结合 $\phi (p^{\alpha })=\phi (2p^{\alpha })$ 可知 $G$ 为模 $2p^{\alpha }$ 的原根。

4. $m\ne 2,4,p^{\alpha },2p^{\alpha }$，其中 $p$ 为奇素数，$\alpha \in {\mathbf{N}}^{\ast }$.

   定理 4

   对于 $m\ne 2,4$，且不存在奇素数 $p$ 及 $\alpha \in {\mathbf{N}}^{\ast }$ 使得 $m=p^{\alpha },2p^{\alpha }$，模 $m$ 的原根不存在。

   证明

   对于 $m=2^{\alpha }$，$\alpha \in {\mathbf{N}}^{\ast },\alpha \ge 3$，则对任意奇数 $a=2k+1$ 均有：

   $$\begin{array}{rl}{a}^{2^{\alpha -2}}& =(2k+1{)}^{2^{\alpha -2}}\\ & \equiv 1+(\genfrac{}{}{0ex}{}{2^{\alpha -2}}{1})(2k)+(\genfrac{}{}{0ex}{}{2^{\alpha -2}}{2})(2k{)}^2(\mathrm{mod}{2}^{\alpha })\\ & \equiv 1+2^{\alpha -1}k+2^{\alpha -1}(2^{\alpha -2}-1)k^2(\mathrm{mod}{2}^{\alpha })\\ & \equiv 1+2^{\alpha -1}(k+(2^{\alpha -2}-1)k^2)(\mathrm{mod}{2}^{\alpha })\\ & \equiv 1(\mathrm{mod}{2}^{\alpha })\end{array}$$

   其中最后一步用到 $k$ 与 $(2^{\alpha -2}-1)k^2$ 同奇偶，故其和为偶数。

   若 $m$ 不是 $2$ 的幂，且 $m$ 为符合题目条件的数，则可设 $m=rt$，这里 $2<r<t$ 且 $(r,t)=1$.

   此时，若 $(a,m)=1$，由欧拉定理可知：

   $$a^{\phi (r)}\equiv 1(\mathrm{mod}r),a^{\phi (t)}\equiv 1(\mathrm{mod}t)$$

   注意到 $n>2$ 时，$\phi (n)$ 为偶数，所以：

   $$a^{\frac{1}{2}\phi (r)\phi (t)}\equiv 1(\mathrm{mod}rt)$$

   进而：

   $${\delta }_m(a)\le {\displaystyle \frac{1}{2}}\phi (r)\phi (t)={\displaystyle \frac{1}{2}}\phi (rt)={\displaystyle \frac{1}{2}}\phi (m)<\phi (m)$$

   由原根定义可得：模 $m$ 的原根不存在。

综合以上 $4$ 个定理，我们便给出了一个数存在原根的充要条件。

最小原根的范围估计

王元²和 Burgess¹证明了素数 $p$ 的最小原根 $g_p=O\left(p^{0.25+ϵ}\right)$，其中 $ϵ>0$.

Fridlander³和 Salié⁴证明了素数 $p$ 的最小原根 $g_p=\mathrm{\Omega }(\log p)$.

这保证了我们暴力找一个数的最小原根，复杂度是可以接受的。

参考资料与注释

1. Primitive root modulo n - Wikipedia

本页面最近更新：2025/3/2 08:28:39，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, Peanut-Tang, 2008verser, bobhan1, CCXXXI, chuxin0816, CroMarmot, Early0v0, Enter-tainer, GavinZhengOI, GeorgePlover, Great-designer, hhc0001, huhaoo, Ir1d, Larry0716, Marcythm, MegaOwIer, opsiff, ouuan, PeterlitsZo, ShelpAm, Tiphereth-A, tml104, wty-yy, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用