原根和阶

阶的定义及求法

称使得 $a^t\equiv 1\pmod p$ 成立的最小正整数 $t_{min}$ 为 $a$ 对模数 $p$ 的阶，记为 $\delta_p(a)$。

有如下定理 ：$\delta_p(a)~|~n\Longleftrightarrow a^n\equiv 1\pmod p$。

又有 $a^{\varphi(p)}\equiv 1\pmod p\Longrightarrow \delta_p(a)~|~\varphi(p)$ 可得一个 $\Theta(\sqrt{p}+\log^2p)$ 求阶的算法：

首先将 $\varphi(p)$ 分解成 $\varphi(p)=k_1^{q_1}\times k_2^{q_2}\times \cdots \times k_r^{q_r}$ 的形式，令 $\delta_p(a)=\varphi(p)$，然后试着用每一个质因子去除 $\delta_p(a)$，如果除了之后 $a^{\frac{\delta_p(a)}{k_i}}\equiv 1\pmod p$ 那么 $\frac{\delta_p(a)}{k_i}$ 就作为新的阶，直到不能再除，此时的 $\delta_p(a)$ 就为 $a$ 在模 $p$ 意义下真正的阶。

原根的定义及求法

原根 $g$ 是使得 $g^{1\sim p-1}$ 在模 $p$ 意义下的值与 $[1,p-1]$ 形成一一对应关系的值。

有如下定理 ：$g$ 为 $p$ 的原根当且仅当 $\delta_p(g)=\varphi(p)$。

于是可以导出一个计算 $g_{min}$ 的算法，从小到大枚举 $g$，若 $\delta_p(g)=\varphi(p)$，则 $g$ 为 $p$ 的最小原根。

有如下定理 ：$g_{min}<p^{\frac{1}{4}}$。

所以以上算法时间复杂度为 $\Theta(\sqrt{p}+p^{\frac{1}{4}}\omega(p))$。