密码学数学基础 笔记 8：从模运算的循环出发，讨论元素的阶、原根的存在与判定、指标的运算法则，以及一般模数下可逆剩余类的结构

阶、原根与指标

上一篇研究了模平方根。这一篇回到模幂本身：反复乘以同一个数，什么时候会回到 $1$？能否只用一个数的幂表示所有可逆剩余类？如果可以，能否把同余方程转化为指数之间的线性关系？

这三个问题分别引出阶、原根和指标。其中指标也叫离散对数，是下一篇密码学应用的起点

从模运算中的循环出发

反复加上一个数

固定 $m\geq2$，从 $b$ 出发反复加上 $a$，得到

$$b,\ b+a,\ b+2a,\ldots\pmod m$$

回到起点的条件是 $b+ka\equiv b\pmod m$，也就是 $m\mid ka$。设 $d=\gcd(a,m)$，则

$$m\mid ka\quad\Longleftrightarrow\quad\frac md\mid k$$

所以每个循环的长度都相同，且全部 $m$ 个剩余类被分成

$$\boxed{\text{循环长度}=\frac m{\gcd(a,m)},\qquad \text{循环个数}=\gcd(a,m)}$$

例如模 $21$ 反复加 $6$，会形成三个长度为 $7$ 的循环，其中一个是

$$0\to6\to12\to18\to3\to9\to15\to0$$

若改为加 $5$，因为 $\gcd(5,21)=1$，便只有一个长度为 $21$ 的循环，从任意起点都能走遍全部剩余类

反复乘以一个数

乘法需要先考虑可逆性。例如模 $21$ 乘以 $6$ 时，$0$ 和 $7$ 都变成 $0$，无法从结果唯一恢复原数

因此把讨论限制在单位群，也就是模 $m$ 的全部可逆剩余类

$$U(m)=(\mathbb Z/m\mathbb Z)^\times =\{[b]_m:\gcd(b,m)=1\},\qquad |U(m)|=\phi(m)$$

若 $a\in U(m)$，乘以 $a$ 的逆操作就是乘以 $a^{-1}$，所以它置换 $U(m)$ 中的元素，每个元素都处于某个循环中。从单位 $b$ 出发，经过 $k$ 步返回的条件是

$$a^kb\equiv b\pmod m \quad\Longleftrightarrow\quad a^k\equiv1\pmod m$$

右侧与起点 $b$ 无关，因此单位群内的所有循环长度相同。这里约去 $b$ 用到了 $b$ 可逆；如果把非单位也放进去，结论就未必成立

元素的阶

设 $\gcd(a,m)=1$。满足 $a^t\equiv1\pmod m$ 的最小正整数 $t$，称为 $a$ 模 $m$ 的阶，记作

$$\boxed{\operatorname{ord}_m(a)=\min\{t\geq1:a^t\equiv1\pmod m\}}$$

欧拉定理保证这样的正整数存在。阶正是前面乘法循环的长度，因此

$$\operatorname{ord}_m(a)\mid\phi(m),\qquad \text{循环个数}=\frac{\phi(m)}{\operatorname{ord}_m(a)}$$

例如模 $21$，$5$ 的幂依次为

$$1,5,4,20,16,17,1$$

所以 $\operatorname{ord}_{21}(5)=6$。$U(21)$ 有 $\phi(21)=12$ 个元素，乘以 $5$ 将它们分成两个循环：

$$\begin{aligned} &1\to5\to4\to20\to16\to17\to1,\\ &2\to10\to8\to19\to11\to13\to2 \end{aligned}$$

什么时候可以约化指数

设 $t=\operatorname{ord}_m(a)$。对任意整数 $k$，都有

$$\boxed{a^k\equiv1\pmod m\quad\Longleftrightarrow\quad t\mid k}$$

负指数通过逆元定义。证明时作带余除法 $k=qt+r$，其中 $0\leq r<t$，于是 $a^k\equiv a^r$。若 $a^k\equiv1$，由 $t$ 的最小性只能有 $r=0$；反方向直接由 $a^t\equiv1$ 得到

进一步，约去 $a^j$ 可得

$$\boxed{a^i\equiv a^j\pmod m \quad\Longleftrightarrow\quad i\equiv j\pmod t}$$

因此，底数和指数处于两个不同的模数下：底数按 $m$ 取模，指数按 $\operatorname{ord}_m(a)$ 取模。由于 $t\mid\phi(m)$，按 $\phi(m)$ 约化指数也成立，但阶给出了准确的周期

幂的阶

若 $a$ 的阶为 $t$，则对整数 $k$，

$$\boxed{\operatorname{ord}_m(a^k)=\frac t{\gcd(t,k)}}$$

因为 $(a^k)^s\equiv1$ 等价于 $t\mid ks$，也就等价于 $t/\gcd(t,k)\mid s$，最小正整数 $s$ 正是右侧

例如 $\operatorname{ord}_{13}(2)=12$，于是

$$\operatorname{ord}_{13}(2^3)=4,\qquad \operatorname{ord}_{13}(2^5)=12$$

特别地，取逆元保持阶不变；取与 $t$ 互素的次幂，也保持阶不变

原根：用一个元素生成全部单位

若 $g$ 满足

$$\boxed{\operatorname{ord}_m(g)=\phi(m)}$$

就称 $g$ 为模 $m$ 的原根。此时

$$1,g,g^2,\ldots,g^{\phi(m)-1}$$

两两不同，恰好表示全部可逆剩余类。换成群论语言，$U(m)$ 是循环群，而 $g$ 是它的生成元

例如模 $13$，有

因此 $2$ 是模 $13$ 的原根。根据幂的阶公式，$2^k$ 也是原根，当且仅当 $\gcd(k,12)=1$。对应 $k=1,5,7,11$，全部原根为 $2,6,11,7$

一般地，只要模 $m$ 存在原根，其全部原根和数量就是

$$\boxed{\{g^k\bmod m:0\leq k<\phi(m),\ \gcd(k,\phi(m))=1\}}$$

$$\boxed{\#\text{原根}=\phi(\phi(m))}$$

素数模数为什么一定存在原根

设 $p$ 是素数，记 $N_d$ 为模 $p$ 阶恰好等于 $d$ 的元素数。由于阶整除 $p-1$，只需要考虑 $d\mid p-1$

先证明 $N_d$ 只能为 $0$ 或 $\phi(d)$。若存在阶为 $d$ 的元素 $a$，那么

$$1,a,\ldots,a^{d-1}$$

是 $x^d-1\equiv0\pmod p$ 的 $d$ 个不同根。模素数时，非零多项式的根数不超过次数，因此该方程的全部根已经列完，任何阶为 $d$ 的元素都在这些幂中

由幂的阶公式，其中恰有 $\phi(d)$ 个元素阶为 $d$。所以 $N_d\in\{0,\phi(d)\}$。另一方面，

$$\sum_{d\mid p-1}N_d=p-1, \qquad \sum_{d\mid p-1}\phi(d)=p-1$$

第二个等式是欧拉函数的因子求和公式。各项 $N_d\leq\phi(d)$，而两边总和相同，因此每一项都相等。特别地，

$$\boxed{N_{p-1}=\phi(p-1)>0}$$

这同时证明了原根的存在性和数量。事实上，对每个 $d\mid p-1$，模 $p$ 都恰有 $\phi(d)$ 个阶为 $d$ 的元素

如何判定一个数是不是原根

若 $\gcd(g,m)=1$，且已知 $\phi(m)$ 的全部不同素因子 $q_1,\ldots,q_s$，则

$$\boxed{g\text{ 是模 }m\text{ 的原根} \quad\Longleftrightarrow\quad g^{\phi(m)/q_i}\not\equiv1\pmod m\quad(1\leq i\leq s)}$$

证明的关键是：若 $t=\operatorname{ord}_m(g)$ 是 $\phi(m)$ 的真因子，就能在 $\phi(m)/t$ 中找到一个素因子 $q_i$，使 $t\mid\phi(m)/q_i$，从而至少一次检查会得到 $1$

例如 $61-1=60=2^2\cdot3\cdot5$，只需检查

$$2^{30}\equiv60,\qquad2^{20}\equiv47,\qquad2^{12}\equiv9\pmod{61}$$

三个结果均不为 $1$，所以 $2$ 是模 $61$ 的原根

给定 $p-1$ 的分解后，可以随机选择候选数再做上述模幂检查。单次选中原根的概率为 $\phi(p-1)/(p-1)$。这里已知群阶的素因数分解是算法的重要前提，不能把分解的成本忽略掉

哪些合数模数存在原根

并非所有单位群都是循环群。例如模 $8$ 的四个单位为 $1,3,5,7$，它们的平方都等于 $1$，所以没有元素的阶达到 $\phi(8)=4$

对 $m\geq2$，完整分类是

$$\boxed{m\text{ 存在原根}\quad\Longleftrightarrow\quad m=2,4,p^r,2p^r}$$

其中 $p$ 是奇素数，$r\geq1$。讲义还把模 $1$ 的平凡情形列入分类，本文统一讨论 $m\geq2$

奇素数的原根可以提升到素数幂

先取模 $p$ 的原根 $g$。因为模 $p$ 的阶整除模 $p^2$ 的阶，而后者又整除 $p(p-1)$，所以

$$\operatorname{ord}_{p^2}(g)\in\{p-1,p(p-1)\}$$

若已经等于 $p(p-1)$，则 $g$ 就是模 $p^2$ 的原根。否则 $g^{p-1}\equiv1\pmod{p^2}$，改用 $g+p$：

$$(g+p)^{p-1}\equiv g^{p-1}+(p-1)g^{p-2}p \equiv1-pg^{p-2}\not\equiv1\pmod{p^2}$$

$g+p$ 模 $p$ 仍是原根，因此它模 $p^2$ 的阶只能为 $p(p-1)$。所以 $g$ 和 $g+p$ 中至少有一个能提升为模 $p^2$ 的原根

进一步，若 $h$ 是模 $p^2$ 的原根，就有

$$h^{p-1}=1+cp,\qquad p\nmid c$$

对奇素数 $p$，二项式展开给出：若 $u=1+cp^s$ 且 $p\nmid c$、$s\geq1$，则

$$u^p\equiv1+cp^{s+1}\pmod{p^{s+2}}$$

反复使用可知 $h^{(p-1)p^{r-1}}-1$ 恰好含有 $r$ 个因子 $p$，因而

$$\operatorname{ord}_{p^r}(h)=p^{r-1}(p-1)=\phi(p^r)$$

于是 $h$ 同时是所有 $p^r$ 的原根。例如 $2$ 是模 $9$ 的原根，因此也是模 $3^7$ 的原根

对于 $2p^r$，若 $h$ 是模 $p^r$ 的原根，在 $h$ 与 $h+p^r$ 中选择奇数代表元。它模 $2$ 的阶为 $1$，模 $p^r$ 的阶为 $\phi(p^r)$，所以模 $2p^r$ 的阶也为 $\phi(p^r)=\phi(2p^r)$

其他情形为什么不行

CRT 将单位群分解为各素数幂模数下单位群的直积。若 $\gcd(m_1,m_2)=1$，则

$$\boxed{\operatorname{ord}_{m_1m_2}(a) =\operatorname{lcm}(\operatorname{ord}_{m_1}(a),\operatorname{ord}_{m_2}(a))}$$

因为 $a^k\equiv1\pmod{m_1m_2}$ 等价于同时在两个模数下等于 $1$，所以 $k$ 必须同时是两个局部阶的倍数

两个不同奇素数幂的欧拉函数都是偶数，它们的最小公倍数严格小于乘积。因此若 $m$ 含有两个不同奇素因子，任何元素的阶都达不到 $\phi(m)$。若 $m$ 同时含有因子 $4$ 和奇素数幂，同样有这个问题

剩下的 $2^r$ 中，$r\geq3$ 时每个奇数 $a$ 都满足

$$a^{2^{r-2}}\equiv1\pmod{2^r}$$

起点是奇数平方模 $8$ 等于 $1$，再逐次平方提升模数。因此阶至多为 $2^{r-2}$，小于 $\phi(2^r)=2^{r-1}$，仍然没有原根

指标：把乘法变成加法

设模 $m$ 有原根 $g$，记 $n=\phi(m)$。每个单位 $a$ 都有唯一的指数类 $k\pmod n$，满足

$$g^k\equiv a\pmod m$$

这个指数类称为以 $g$ 为底的指标，记作 $\operatorname{ind}_{m,g}(a)$，也记作 $\log_g a$。本文用 $0\leq k<n$ 作为代表元，所以 $\operatorname{ind}(1)=0$；讲义表中用 $n$ 表示它，两者是同一个指数类

由指数运算法则，指标满足

$$\begin{aligned} \operatorname{ind}(ab)&\equiv\operatorname{ind}(a)+\operatorname{ind}(b)\pmod n,\\ \operatorname{ind}(a^k)&\equiv k\operatorname{ind}(a)\pmod n,\\ \operatorname{ind}(a^{-1})&\equiv-\operatorname{ind}(a)\pmod n \end{aligned}$$

因此乘法变成加法，乘幂变成乘法。指标只对单位定义，并且指标之间的同余应按 $n$ 取模，而不是按原来的 $m$

用指标求解幂同余

考虑 $a\in U(m)$、$k\geq1$ 时的方程

$$x^k\equiv a\pmod m$$

任何解 $x$ 都必须可逆。令 $x=g^y$、$a=g^b$，原方程等价于

$$ky\equiv b\pmod n$$

设 $d=\gcd(k,n)$，由线性同余方程的结论，

$$\boxed{x^k\equiv a\pmod m\text{ 有解} \quad\Longleftrightarrow\quad d\mid\operatorname{ind}(a)}$$

有解时恰有 $d$ 个不同的解，因为每个指数解类都对应一个不同的单位

例如模 $13$ 解 $x^4\equiv3$。以 $2$ 为原根，$3\equiv2^4$，所以

$$4y\equiv4\pmod{12} \quad\Longleftrightarrow\quad y\equiv1\pmod3$$

模 $12$ 的指数解为 $1,4,7,10$，转回原来的剩余类得到

$$\boxed{x\equiv2,3,11,10\pmod{13}}$$

素数模数下，还可以不计算指标，直接判断幂剩余。若 $p\nmid a$，$d=\gcd(k,p-1)$，则

$$\boxed{x^k\equiv a\pmod p\text{ 有解} \quad\Longleftrightarrow\quad a^{(p-1)/d}\equiv1\pmod p}$$

因为写成 $a=g^b$ 后，右侧等价于 $(p-1)\mid b(p-1)/d$，即 $d\mid b$。取 $k=2$ 就回到上一篇的欧拉判别法

换底公式

若 $h=g^c$ 也是原根，则 $\gcd(c,n)=1$。对任意单位 $a$，

$$\boxed{\operatorname{ind}_h(a) \equiv c^{-1}\operatorname{ind}_g(a)\pmod n}$$

因为 $a=h^y=g^{cy}$，所以 $\operatorname{ind}_g(a)\equiv cy\pmod n$。例如模 $13$ 的另一个原根为 $6=2^5$，$5^{-1}\equiv5\pmod{12}$，故

$$\operatorname{ind}_6(3)\equiv5\cdot4\equiv8\pmod{12}$$

换底公式说明，若能求解同一个循环群中任意输入的离散对数，就可以转换生成元；但换底系数 $c$ 本身也是离散对数，不能在未求出它时直接当成已知量

没有原根时：用一组指标描述单位

没有原根意味着无法只用一个指数描述全部单位，但仍可借助局部分解建立坐标

模 $2^r$ 的特殊结构

当 $r\geq3$ 时，虽然 $U(2^r)$ 不是循环群，却有

$$\boxed{\operatorname{ord}_{2^r}(5)=2^{r-2}}$$

证明可从下面的同余式逐次平方得到：

$$5^{2^{r-3}}\equiv1+2^{r-1}\pmod{2^r}$$

它表明 $5^{2^{r-3}}$ 尚未回到 $1$，再平方则回到 $1$。同时 $5\equiv1\pmod4$，其 $2^{r-2}$ 个不同幂恰好覆盖所有模 $4$ 为 $1$ 的单位

每个奇数都能唯一表示为

$$\boxed{a\equiv(-1)^\varepsilon5^t\pmod{2^r},\qquad \varepsilon\in\{0,1\},\quad0\leq t<2^{r-2}}$$

符号由 $a\bmod4$ 决定，$\varepsilon\equiv(a-1)/2\pmod2$，所以

$$U(2^r)\cong C_2\times C_{2^{r-2}}$$

其中 $C_s$ 表示 $s$ 阶循环群。例如模 $16$ 的 $5$ 的幂为 $1,5,9,13$，再取相反数得到其余四个单位 $15,11,7,3$

CRT 与一般指标组

若

$$m=2^\alpha\prod_{i=1}^s p_i^{e_i}$$

其中 $p_i$ 是互不相同的奇素数，则

$$U(m)\cong U(2^\alpha)\times\prod_{i=1}^s U(p_i^{e_i})$$

当 $\alpha=0$ 时省略 $2$ 的分量；$U(2)$ 是平凡群，$U(4)$ 由 $-1$ 生成，$\alpha\geq3$ 时则使用前面的两个坐标

在每个奇素数幂下选择原根 $g_i$，将 $a$ 写成局部幂 $g_i^{t_i}$。若 $\alpha\geq3$，再加入 $(-1)^\varepsilon5^t$ 的两个指数。这样得到的指标组，在各自的周期内唯一确定单位 $a$

例如模 $40=8\cdot5$，$a=3$ 的局部表示为

$$3\equiv(-1)^1 5^1\pmod8,\qquad 3\equiv2^3\pmod5$$

它对应指标组 $(1,1;3)$，三个坐标分别按 $2,2,4$ 取模。两个单位相乘，只需将对应指标相加，再用 CRT 还原剩余类

所有单位的公共周期

将各个局部群的周期取最小公倍数，得到 Carmichael 函数 $\lambda(m)$：

$$\lambda(p^e)=\phi(p^e)\quad(p\text{ 为奇素数})$$

$$\lambda(2^\alpha)= \begin{cases} 1,&\alpha=1,\\ 2,&\alpha=2,\\ 2^{\alpha-2},&\alpha\geq3 \end{cases}$$

对于一般 $m$，$\lambda(m)$ 是各素数幂分量的 $\lambda$ 值的最小公倍数。因此

$$\boxed{\operatorname{ord}_m(a)\mid\lambda(m)\mid\phi(m), \qquad a^{\lambda(m)}\equiv1\pmod m}$$

例如 $\lambda(40)=\operatorname{lcm}(2,4)=4$，而 $\phi(40)=16$，所以模 $40$ 的任何单位的阶都不可能达到 $16$

从指标走向离散对数

原根给出了一个对应关系：

$$\mathbb Z/\phi(m)\mathbb Z\longrightarrow U(m),\qquad k\longmapsto g^k$$

它把指数的加法转成单位的乘法，是两个群之间的同构。正向可以通过快速模幂高效计算，反向则要求给定 $a$ 求出 $k$，也就是计算离散对数

小模数下可以列指标表；模数增大后，表的大小随群阶增长，便需要其他算法。下一篇将从这个正向与反向计算的差异出发，讨论 Diffie–Hellman 密钥交换、ElGamal 加密，以及求解离散对数的主要方法