1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
bool isPrimitive(ll g, ll n, ll phi, map<ll, int>& phiFacts) {
if (g == 1) return n == 2;
if (gcd(g, n) > 1) return false;
for (auto [f, _] : phiFacts)
if (powMod(g, phi / f, n) == 1) return false;
return true;
}
bool isPrimitive(ll g, ll n) {
ll phin = phi(n); //isPrime(n) => phi(n) = n - 1
map<ll, int> phiFacts;
factor(phin, phiFacts);
return isPrimitive(g, n, phin, phiFacts);
}
ll findPrimitive(ll n) { //test auf existens geht schneller
ll phin = phi(n); //isPrime(n) => phi(n) = n - 1
map<ll, int> phiFacts;
factor(phin, phiFacts);
for (ll res = 1; res < n; res++) // oder zufällige Reihenfolge
if (isPrimitive(res, n, phin, phiFacts)) return res;
return -1;
}
|
