指数

• 定义：设 $(a,m)=1$，使 $a^d\equiv 1(\mathrm{mod}m)$ 成立的最小正整数 $d$，记为 $or{d}_m(a)$。
  • 简单说，就是一个数在模 m 意义下，通过反复自乘回到 “单位元（1）” 所需的最小次数。
• 性质：
  1. $a^k\equiv 1(\mathrm{mod}m)⟺or{d}_m(a)\mid k$。
  2. $or{d}_m(a)\mid \varphi (m)$（由欧拉定理可知）。
  3. $or{d}_m(a^k)=\frac{or{d}_m(a)}{\gcd (or{d}_m(a),k)}$。

求解步骤：

• 步骤 1: 确保互素性首先，检查 $a$ 和 $n$ 是否互素。如果 $\gcd (a,n)\ne 1$，则 $a$ 模 $n$ 的阶不存在。如果 $\gcd (a,n)=1$，则阶 ${\text{ord}}_n(a)$ 存在，并且是 $\varphi (n)$ 的因子。
• 步骤 2: 计算欧拉函数 $\varphi (n)$计算模 $n$ 的欧拉函数值 $\varphi (n)$。分解 $n$： 将 $n$ 分解为标准素数幂形式：$n=p_1^{e_1}{p}_2^{e_2}\cdots p_r^{e_r}$计算 $\varphi (n)$： 使用欧拉$\varphi$函数的乘积公式：$\varphi (n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_r}\right)$或使用更便于计算的形式：$\varphi (n)=\varphi (p_1^{e_1})\varphi (p_2^{e_2})\cdots \varphi (p_r^{e_r})$其中 $\varphi (p^e)=p^e-p^{e-1}=p^{e-1}(p-1)$。
• 步骤 3: 确定候选阶数 $k$找到 $\varphi (n)$ 的所有正因子（包括 1 和 $\varphi (n)$ 本身）。$\text{Candidate set }K=\{k\mid k\text{ is a positive divisor of }\varphi (n)\}$
• 步骤 4: 检验并找到最小阶数从小到大依次检验 $K$ 中的因子 $k$。最小的满足 $a^k\equiv 1(\mathrm{mod}n)$ 的 $k$ 就是 ${\text{ord}}_n(a)$。优化技巧： 不必检验所有因子。只需检验所有 $\varphi (n)$ 的最大真因子（即 $\frac{\varphi (n)}{p_i}$，其中 $p_i$ 是 $\varphi (n)$ 的素因子）。如果 $a^{\varphi (n)/p_i}\not\equiv 1(\mathrm{mod}n)$ 对所有 $\varphi (n)$ 的素因子 $p_i$ 都成立，那么阶数就是 $\varphi (n)$。