原根的算法

hbghlyj

Algorithm for finding a primitive root重述如下：

一个朴素的算法是考虑范围内的所有数$[1, n-1]$，然后检查每个数是否是原根（计算其$1,\dots,n-1$次幂然后检查它们是否互不相同）。这个算法的复杂度为$O(g \cdot n)$，速度太慢。在本节中，我们提出了一种更快的算法，利用了几个著名的定理。

根据前一节的内容，我们知道如果最小的满足$g^k \equiv 1 \pmod n$的数$k$是$\phi (n)$，那么$g$就是一个原根。由于对于任何与$n$互质的数$a$，根据欧拉定理，我们知道$a ^ { \phi (n) } \equiv 1 \pmod n$，因此要检查$g$是否是原根，只需检查对于所有小于$\phi (n)$的$d$，$g^d \not \equiv 1 \pmod n$。然而，这个算法仍然太慢。

根据拉格朗日定理，任何数模$n$的阶必须是$\phi (n)$的一个因子。因此，只需验证所有真因子$d \mid \phi (n)$是否满足$g^d \not \equiv 1 \pmod n$。这已经是一个快得多的算法，但我们还可以进一步改进。

将$\phi (n)$分解质因数$\phi (n) = p_1 ^ {a_1} \cdots p_s ^ {a_s}$。我们证明在前面的算法中，只需考虑具有形式$\frac { \phi (n) } {p_j}$的$d$的值就足够了。事实上，设$d$是$\phi (n)$的任何真因子。显然，存在这样的$j$使得$d \mid \frac { \phi (n) } {p_j}$，即$d \cdot k = \frac { \phi (n) } {p_j}$。然而，如果$g^d \equiv 1 \pmod n$，我们会得到：
$$g ^ { \frac { \phi (n)} {p_j} } \equiv g ^ {d \cdot k} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$$
也就是说，在形如$\frac {\phi (n)} {p_i}$的数中，至少会有一个不满足条件。

现在我们有了一个完整的寻找原根的算法：

[*] 首先，找到$\phi (n)$并进行因数分解。

[*] 然后遍历所有数$g \in [1, n]$，检查它是否是原根：

• 计算所有$g ^ { \frac {\phi (n)} {
  p_i}} \pmod n$的值。
• 如果所有计算得到的值都$\ne1$，则$g$是一个原根。

该算法的运行时间复杂度为$O(\text{Ans}\cdot \log \phi (n) \cdot \log n)$（假设$\phi (n)$具有$\log \phi (n)$个因子）。