p is prime
| 12 | } |
| 13 | // p is prime |
| 14 | int primitive_root(int p) { |
| 15 | vector<int> fact; |
| 16 | int phi = p - 1, n = phi; |
| 17 | for (int i = 2; i * i <= n; ++i) { |
| 18 | if (n % i == 0) { |
| 19 | fact.push_back(i); |
| 20 | while (n % i == 0) n /= i; |
| 21 | } |
| 22 | } |
| 23 | if (n > 1) fact.push_back(n); |
| 24 | for (int res = 2; res <= p; ++res) { // this loop will run at most (logp ^ 6) times i.e. until a root is found |
| 25 | bool ok = true; |
| 26 | // check if this is a primitive root modulo p |
| 27 | for (size_t i = 0; i < fact.size() && ok; ++i) |
| 28 | ok &= power(res, phi / fact[i], p) != 1; |
| 29 | if (ok) return res; |
| 30 | } |
| 31 | return -1; |
| 32 | } |
| 33 | // returns any or all numbers x such that x ^ k = a (mod m) |
| 34 | // existence: a = 0 is trivial, and if a > 0: a ^ (phi(m) / gcd(k, phi(m))) == 1 mod m |
| 35 | // if solution exists, then number of solutions = gcd(k, phi(m)). |
no test coverage detected