模运算下的指数与原根 模运算下的指数是数论中刻画整数在模 \( n \) 下的周期性质的重要概念。设 \( a \) 和 \( n \) 为正整数且 \( \gcd(a, n) = 1 \)， 指数 （或阶）定义为满足 \[ a^k \equiv 1 \pmod{n} \] 的最小正整数 \( k \)，记作 \( \text{ord}_ n(a) \)。例如，取 \( n=7 \)，计算 \( a=2 \) 的幂模 7： \[ 2^1 \equiv 2, \quad 2^2 \equiv 4, \quad 2^3 \equiv 1 \pmod{7} \] 因此 \( \text{ord}_ 7(2) = 3 \)。 性质 ： 指数必整除欧拉函数 \( \varphi(n) \)（由欧拉定理 \( a^{\varphi(n)} \equiv 1 \pmod{n} \) 可得）。 若 \( a^m \equiv 1 \pmod{n} \)，则 \( \text{ord}_ n(a) \mid m \)。 原根的定义与存在性 若 \( \text{ord}_ n(a) = \varphi(n) \)，则称 \( a \) 为模 \( n \) 的一个 原根 。例如，模 7 的欧拉函数 \( \varphi(7)=6 \)，验证 \( a=3 \)： \[ 3^1 \equiv 3, \quad 3^2 \equiv 2, \quad 3^3 \equiv 6, \quad 3^4 \equiv 4, \quad 3^5 \equiv 5, \quad 3^6 \equiv 1 \pmod{7} \] 指数为 6，故 3 是模 7 的原根。 关键结论 ： 原根存在的模 \( n \) 仅限于 \( 1, 2, 4, p^k, 2p^k \)（其中 \( p \) 为奇素数）。 若原根存在，则模 \( n \) 的原根个数为 \( \varphi(\varphi(n)) \)。 原根与简化剩余系的关系 设 \( g \) 为模 \( n \) 的原根，则集合 \[ \{ g^1, g^2, \dots, g^{\varphi(n)} \} \] 构成模 \( n \) 的 简化剩余系 （即所有与 \( n \) 互素的剩余类）。这一性质可将乘法问题转化为指数加法问题，类似对数运算。 指数计算与算法 求指数的步骤 ： 计算 \( \varphi(n) \) 并分解质因数： \( \varphi(n) = p_ 1^{e_ 1} p_ 2^{e_ 2} \cdots p_ k^{e_ k} \)。 对每个素因子 \( p_ i \)，计算 \( a^{\varphi(n)/p_ i} \pmod{n} \)： 若结果不为 1，则保留该因子； 若结果为 1，则尝试 \( a^{\varphi(n)/p_ i^2} \) 等，直至确定指数中 \( p_ i \) 的幂次。 找原根的算法 ： 随机选取与 \( n \) 互素的 \( a \)，计算其指数； 若指数等于 \( \varphi(n) \)，则找到原根；否则继续尝试。 应用：离散对数问题 原根的存在引出了 离散对数 概念：若 \( g \) 为模 \( n \) 的原根，对任意与 \( n \) 互素的 \( b \)，存在唯一整数 \( k \in [ 1, \varphi(n) ] \) 使得 \[ g^k \equiv b \pmod{n} \] 记 \( k = \log_ g b \)。离散对数的计算困难性是现代密码学（如 Diffie-Hellman 密钥交换）的基础。