Untitled
unknown
plain_text
5 months ago
1.4 kB
4
Indexable
#include <iostream> #include <cmath> #include <vector> using namespace std; int euler_totient(int n) { int result = n; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { while (n % i == 0) { n /= i; } result -= result / i; } } if (n > 1) { result -= result / n; } return result; } bool is_primitive_root(int g, int n) { int phi_n = euler_totient(n); vector<int> divisors; for (int i = 1; i * i <= phi_n; ++i) { if (phi_n % i == 0) { divisors.push_back(i); if (i != phi_n / i) { divisors.push_back(phi_n / i); } } } for (int i = 0; i < divisors.size(); ++i) { int d = divisors[i]; if (d == phi_n) continue; if (pow(g, d) - (int)pow(g, d) / n == 1) { return false; } } return true; } int main() { int n, g; cout << "Enter modulus n: "; cin >> n; cout << "Enter candidate g: "; cin >> g; if (is_primitive_root(g, n)) { cout << g << " is a primitive root modulo " << n << endl; } else { cout << g << " is not a primitive root modulo " << n << endl; } return 0; }
Editor is loading...
Leave a Comment