| 求奇素数的原根 | 您所在的位置：网站首页 › 求质数程序 › 求奇素数的原根 |
求奇素数的原根
|
1.程序说明
输入：一个奇素数m 输出：按序输出m的所有原根 运行结果： 
与课本样例进行对比： 
2.实现思路
判断是否与1模m同余 bool yi(double x, int m) { x -= 1; if (fmod(x,m) == 0) { return true; } else { return false; } }//判断是否与1模m同余判断两个数是否互素 bool husu(int x,int m) { int i = 0; while (x != 0) { i = m % x; m = x; x = i; } if (m == 1) { return true; } return false; }//判断是否x与m互素即使用欧几里得辗转相除法求x和m的最大公因数是否为1，实现思路可以参考此博文 实现素因子的分解 //以下用于求素因子分解 int n = oula;//记录欧拉函数值 int i = 2; int num = 0;//用于计算有多少个不同的素因子 int a[100] = { 0 }; while (n != 1) { while (n % i == 0) { if (num == 0) { a[num] = i; num++; } else if (a[num-1] != i) { a[num] = i; num++; } n /= i; } i++; }使用了算术基本定理实现分解，可以参考此博文 求出最小原根g //以下为求最小原根 for (int i = 0; i < num; i++) { a[i] = oula / a[i]; } int g = 2; bool fail = true; int j = 0; while (fail) { for (j = 0; j < num; j++) { tem = pow(g, a[j]); if (yi(tem, m)) { break; } } if (j == num) { fail = false;//此时g即为最小原根 } else { g++; } }求出缩系，最终借助缩系求出所有原根 //以下为求缩系. int* b = new int[oula]; int count = 0;//用于计算缩系中元素的个数 for (int i = 1; i < m; i++) { if (husu(i, oula)) { b[count] = i; count++; } } //最后，求所有原根 int *ans = new int[count]; for (int i = 0; i < count; i++) { if (i == 0) { tem = pow(g, b[i]); ans[i] = fmod(tem, m); } else { ans[i] = ans[i - 1]; for (int k = b[i - 1]; k < b[i]; k++) { ans[i] *= g;//这里简化计算，若直接求高次幂，容易因为精度不够产生错误。 } ans[i] = fmod(ans[i], m); } cout |
【本文地址】
公司简介
联系我们