$\S 5.2 $ 原根

一、指数（离散对数）

定义

设 $g$ 是模 $m$ 的一个原根（即 $\operatorname{ord}_m(g) = \varphi(m)$）. 则对任意满足 $\gcd(a, m) = 1$ 的 $a$，存在唯一的整数 $t$（$0 \le t < \varphi(m)$）使得

\[ a \equiv g^t \pmod{m} \]

称 $t$ 为 $a$ 对底数 $g$ 的指数，记作 $\operatorname{ind}_g(a) = t$（也常写作 $\operatorname{ind}(a)$ 当底数明确时）.

指数可以理解为模 $m$ 下的"对数"：$a = g^{\operatorname{ind}_g(a)} \pmod{m}$.

性质 1 — 指数的模

\[ a \equiv b \pmod{m} \iff \operatorname{ind}(a) \equiv \operatorname{ind}(b) \pmod{\varphi(m)} \]

性质 2 — 乘法变加法

\[ \operatorname{ind}(ab) \equiv \operatorname{ind}(a) + \operatorname{ind}(b) \pmod{\varphi(m)} \]

这恰如对数 $\log(ab) = \log a + \log b$.

性质 3 — 幂次变乘法

\[ \operatorname{ind}(a^k) \equiv k \cdot \operatorname{ind}(a) \pmod{\varphi(m)} \]

性质 4 — 换底公式

若 $g_1, g_2$ 都是模 $m$ 的原根，则

\[ \operatorname{ind}_{g_2}(a) \equiv \operatorname{ind}_{g_2}(g_1) \cdot \operatorname{ind}_{g_1}(a) \pmod{\varphi(m)} \]

性质 5 — 次数与指数的关系

设 $\operatorname{ord}_m(a) = l$，则 $\gcd(\operatorname{ind}(a), \varphi(m)) = \dfrac{\varphi(m)}{l}$.

特别地，$a$ 是原根 $\iff$ $\gcd(\operatorname{ind}(a), \varphi(m)) = 1$.

证明：$a^l \equiv 1 \pmod{m} \iff g^{l \cdot \operatorname{ind}(a)} \equiv 1 \pmod{m} \iff \varphi(m) \mid l \cdot \operatorname{ind}(a)$.

令 $d = \gcd(\operatorname{ind}(a), \varphi(m))$，则 $\frac{\varphi(m)}{d} \mid l$，而 $l$ 是最小正指数使 $a^l \equiv 1$，故 $l = \frac{\varphi(m)}{d}$. $\quad \square$

二、指数表

当模数 $m$ 较小时，可以为每个与 $m$ 互素的 $a$ 列出其指数，形成指数表，方便求解同余式.

例题

模 $7$，取原根 $g = 3$（$\varphi(7) = 6$）：

$a$	1	2	3	4	5	6
$\operatorname{ind}_3(a)$	0	2	1	4	5	3

验证：$3^0 \equiv 1,\ 3^2 = 9 \equiv 2,\ 3^1 = 3,\ 3^4 = 81 \equiv 4,\ 3^5 = 243 \equiv 5,\ 3^3 = 27 \equiv 6 \pmod{7}$.

利用指数表，同余式 $ax \equiv b \pmod{p}$ 可化为 $\operatorname{ind}(a) + \operatorname{ind}(x) \equiv \operatorname{ind}(b) \pmod{p-1}$，从而 $\operatorname{ind}(x) \equiv \operatorname{ind}(b) - \operatorname{ind}(a) \pmod{p-1}$，查表即得 $x$.