math/primitiveRoot.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Ist g Primitivwurzel modulo p. Teste zufällige g, um eine zu finden.
bool is_primitive(ll g, ll p) {
  map<ll, int> facs;
  factor(p - 1, facs);
  for (auto &f : facs)
    if (1 == powMod(g, (p - 1) / f.first, p)) return false;
  return true;
}

// Alternativ: Generator zum Finden. -1 falls keine existiert.
ll generator (ll p) { // Laufzeit: O(ans*log(phi(n))*log(n))
	map<ll, int> facs;
	factor(n, facs);
  ll phi = phi(p),  n = phi;

  for (ll res = 2; res <= p; res++) {
    bool ok = true;
    for (auto &f : facs)
    	ok &= powMod(res, phi / f.first, p) != 1;
    if (ok)  return res;
  }
  return -1;
}