素数求原根

1 模m原根的定义

1.1符号说明:

$Z_m^{\ast }$:代表满足$1<=i<=m-1,(i,m)=1$的数字$i$组成的集合
$or{d}_m(a)$:代表$a(modm)$在$Z_m^{\ast }$中的阶，即使得$a^d\equiv 1$的最小正整数$d$。
$\phi (m)$:数$m$简化剩余系中的元素个数，即集合$Z_m^{\ast }$中的元素个数。

1.2定义

若$or{d}_m(a)=\phi (m)$，则称$a$为模$m$的原根。即在$Z_m^{\ast }$的乘法上的生成元。

2 素数求原根

2.1 理论基础

$\phi (m)=m-1=p_i^a\ast p_j^b...p_k^c(p_i,p_j...p_k$为素数$)$。对于任意一个$p_i$，都满足$a^{\phi (m)/p_i}\not\equiv 1(\mathrm{mod}m)$，则$a$为模$m$的原根。
证明： 根据拉个格朗日定理，对于任意一个$a$ $\in$$Z_m^{\ast }$，有 $or{d}_m(a)$ | $\phi (m)$，即当且仅当d|$\phi (m)$时，才会使得$a^d\equiv 1(\mathrm{mod}m)$。
根据模m原根的定义，要求$or{d}_m(a)=\phi (m)$，即当且仅当$d=\phi (m)$时，才有$a^d\equiv 1(\mathrm{mod}m)$。

进一步地推导可知，$d\ne \phi (m)$且d|$\phi (m)$时，若对于所有d都满足$a^d\not\equiv 1(\mathrm{mod}m)$，则a为原根 (条件一) 。

对于任意一个$d$，因为$d\ne \phi (m)$且d|$\phi (m)$，因此存在i，使得$d|$$\phi (m)/p_i$，由于$a^d\not\equiv 1(\mathrm{mod}m)$，因此可以推导出$a^{\phi (m)/p_i}\not\equiv 1(\mathrm{mod}m)$。

因此，若对于所有$p_i$，满足$a^{\phi (m)/p_i}\not\equiv 1(\mathrm{mod}m)$，则a为原根 (条件二) 。

拉格朗日定理：在有限群$<G,\ast >$中，每个元素的周期是#$G$(集合G的元素的个数)的因子。

2.2 算法流程

算法的整体思路是根据2.1节所述的条件二来制定的。其具体的流程如下：
step1: 使用素数线性筛法，找出$1$到$m$中的所有素数。
step2: 确定m的质因子集合{$p_i$}。
step3: 遍历$2$到$m$中的所有数，假设当前处理的数为a。遍历m的所有质因子，若都满足 $a^{\phi (m)/p_i}$ $\not\equiv$ 1 $(\mathrm{mod}m)$，则a为模m的原根。

2.3代码实现

#include<iostream>
using namespace std;
#define NUM 998244380
bool is_prime[NUM] = { 0 };
#define NMAX 400000
long long prime[NMAX];
long long prime_num = 0;
long long m;//待处理的素数
long long p_factor[NMAX];
long long p_factor_num = 0;
void get_prime(long long n) {for (long long m = 2; m < n; m++) {if (m == 98244379){cout << m << endl;}if (m == 298244379){cout << m << endl;}//数m没有被筛选过if (!is_prime[m]) {if (prime_num > NMAX) {cout << "越界" << endl;}prime[prime_num++] = m;}//筛选掉以prime[i]为最小素因子的合数m*prime[i]for (long long i = 0; i < prime_num; i++) {if ((m * prime[i]) < n) is_prime[m * prime[i]] = 1;if (m % prime[i] == 0) break;//m*prime[j](j>i)的最小素因子为m的最小素因子prime[i]而非prime[j]，因此跳出循环}}//打印输出/*for (int i = 0; i < prime_num; i++) {cout << prime[i] << " ";}cout << endl;*/
}
void get_p_factor(long long m) {p_factor_num = 0;for (long long i = 0; i < prime_num; i++) {if ((m - 1) % prime[i] == 0) p_factor[p_factor_num++] = prime[i];}
}
long long ksm(long long a, long long d, long long mod) {long long ret = 1;while (d) {if ((d & 1) == 1) ret = (ret * a) % mod;//按位与为&,而&&代表的是条件与a = (a * a) % mod;d >>= 1;}return ret;
}
int judge(long long a) {for (long long i = 0; i < p_factor_num; i++) {if (ksm(a, (m - 1) / p_factor[i], m) == 1) {return 0;}}return 1;
}
int main() {//1.获取所有的素数get_prime(1000);while (cin >> m) {//获取m的所有质因子get_p_factor(m);//遍历2...m-1进行判断for (long long a = 2; a < m; a++) {if (judge(a)) {cout << a << endl;break;}}}
}