初等数论入门 Lesson 7 阶与原根

阶

Order

定义：

对于 $\gcd(a,m)=1$

$$\operatorname{ord}_m(a)=\min\{n\in \mathbb Z\mid a^n\equiv 1\pmod m\}$$

即不断计算 $a^1,a^2,\dots$，第一次出现余数为1，那个指数就是阶。

存在性证明：

由欧拉定理 $a^{\varphi(m)}\equiv 1\pmod m$

阶的定理

整除性定理

$$a^k\equiv 1\pmod m\iff \operatorname{ord}_m(a)\mid k$$

且一定有：

$$\operatorname{ord}_m(a)\le\varphi(m)$$

降幂公式

$$a^k\equiv a^{k\;\bmod\; \operatorname{ord}_m(a) }\pmod m$$

原根

Primitive Root

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

原根存在性

模 $m$ 存在原根的充要条件是：

$$m=2,\;4,\;p^k,\;2p_k$$

其中 $p$ 是奇素数

简化判定法

我们一个个判断 $m$ 的 $\varphi(m)$ 个素因子，若为原根，则满足：

$$g^{\varphi(m)/qi}\not\equiv1\pmod m$$

既约剩余系生成

若 $g$ 为模 $m$ 的一个原根，则集合：

$$\{g^1,g^2,\dots,g^{\varphi(m)}\}$$

恰好构成 $m$ 的一个缩系

原根个数

若 $m$ 存在原根，则恰有 $\varphi(\varphi(m))$ 个

证明：

若 $g$ 为一个原根，则剩余原根必然可以表示为 $g^k$ （因为 $g^k$ 取满 $m$ 的缩系）

又：

$$\operatorname{ord}_m(g^k)=\dfrac{\varphi (m)}{\gcd(k,\varphi(m))}$$

因此合法的 $k$ 有 $\varphi(\varphi(m))$ 个

离散对数

若 $\gcd(a,m)=1$，则存在**唯一正整数 $k\;(1\le k \le \varphi(m) )$ **

$$g^k\equiv a\pmod m \Rightarrow k=\operatorname{ind}_g(a)$$

$k$ 称为 $a$ 以 $g$ 为底的离散对数（Discrete Logarithm

运算性质：和普通对数相同

• 关系性质：单向性

已知 $g,k,m$，可以快速求 $a$

已知 $g,a,m$，难求 $k$

这是现代密码体制的基石