模为奇素数的原根求解

2019-04-13 13:02发布

此问题的基本思路:

定理:设p为奇素数,p-1的所有不同素因数q1,q2,......,qsq_1,q_2,......,q_s,则g是模p原根的充要条件是

g(p1)qig^{frac{(p-1)}{q_i}} eq 1(mod p),i=1,2,…,s

注: eq代表不同余
  1. 求任一原根g
    ①求p-1的素因数q1,q2,.......,qsq_1,q_2,.......,q_s
    ②求得e=(p1)qifrac{(p-1)}{q_i}, q1,q2,.......,qsq_1,q_2,.......,q_s
    ③判断ge^e(mod p)是否同余1,g为2,3,4,5,…等,逐个验算,求得某一个原根g
  2. 求d,使d满足(d,p-1)=1
  3. 求gd^d(mod p),其解遍历模p的所有原根。
下面是实现代码(此代码采用int保存所有数据) #include #include #define MAX_NUM 500 using namespace std; //判断一个数是否为素数 bool IsPrime(int n) { if (n == 1) return false; if (n == 2) return true; int sqrtn = (int)sqrt(n); for (int i = 2; i < sqrtn + 1; i++) if (n%i == 0) return false; return true; } //如果数n是个素数,则直接添加到素因数数组pri_factor,并终止此函数。 //否则,从[2,∞]中寻得素数,将其添加到数组并除以n。 //求一个数n的素因数,返回数组大小 int PrimeFactor(int *pri_factor, int n) { int index = 0;//用于数组去重并记录数组大小 while (!IsPrime(n)){ for (int i = 2; i < n / 2 + 1; i++){ if (IsPrime(i)&&n%i==0){//找到一个素因数i if (index > 0 && pri_factor[index - 1] == i) index--; pri_factor[index++] = i; n /= i; break; } } } if (index == 0) pri_factor[index++] = n; else if(n!=pri_factor[index-1]) pri_factor[index++] = n; return index; } //a的e次幂(mod p) int IntModPow(int a, int e, int p) { int factor = 1;//积 for (int i = 0; i < e; i++){ factor *= a; if (factor > p) factor %= p; } return factor; } //求某一原根 int OneRoot(int *pri_factor,int len_array,int p) { int g = 2; int *q; q = new int[len_array]; for (int i = 0; i < len_array; i++) q[i] = (p - 1) / pri_factor[i]; for (int i = 0; i < 65535; i++){ //sign为1表示g的q[j]次幂模p同余1 int j,sign=0; for (j = 0; j < len_array; j++){ //若g的q[j]次幂模p同余1,则不合定理 //跳过此g if (IntModPow(g, q[j], p) == 1){ sign = 1; break; } } //遍历q[j],满足g的q[j]次幂模p不同余1, //则说明g为原根 if (!sign&&j == len_array){ delete[]q; return g; } g++; } //若原根未找到,则返回0 delete[]q; return 0; } //求两个数的最大公约数 int GcdNum(int a, int b) { while (a != b){ if (a%b == 0) return b; if (b%a == 0) return a; if (a > b) a %= b; else if (a < b) b %= a; } return a; } //求与n互素的d,返回数组大小 int RootE(int *d, int n) { int index = 0; for (int i = 1; i < n; i++) if (GcdNum(i, n) == 1) d[index++] = i; return index; } //主函数 int main() { int p;//模 int pri_factor[MAX_NUM];//素因数 int d[MAX_NUM];//原根的指数 while (1){ cin >> p; int len_pri=PrimeFactor(pri_factor,p-1); int one_root=OneRoot(pri_factor, len_pri, p); if (one_root == 0){ cout << "未找到原根" << endl; return 0; } int len_d = RootE(d, p - 1); cout << "原根的个数:" << len_d << endl; cout << "原根分别为:"; for (int i = 0; i < len_d; i++) cout << IntModPow(one_root, d[i], p) << " "; cout << endl; } return 0; } 注:若有错误,欢迎大家在评论区指正。