numtheory/primitiveRoot.cpp

View this file on GitHub
Last update: 2024-04-05 18:02:52+08:00

Verified with

test/primitive_root.test.cpp

Code

//#include "numtheory/fastFactorize.cpp"

ull primitiveRoot(ull p) {
  auto fac = factor(p - 1);
  ranges::sort(fac);
  fac.resize(unique(fac.begin(), fac.end()) - fac.begin());
  auto test = [p, fac](ull x) {
    for(ull d : fac)
      if (modpow(x, (p - 1) / d, p) == 1)
        return false;
    return true;
  };
  static mt19937_64 rng(clock);
  uniform_int_distribution<ull> unif(1, p - 1);
  ull root;
  while(!test(root = unif(rng)));
  return root;
}

#line 1 "numtheory/primitiveRoot.cpp"
//#include "numtheory/fastFactorize.cpp"

ull primitiveRoot(ull p) {
  auto fac = factor(p - 1);
  ranges::sort(fac);
  fac.resize(unique(fac.begin(), fac.end()) - fac.begin());
  auto test = [p, fac](ull x) {
    for(ull d : fac)
      if (modpow(x, (p - 1) / d, p) == 1)
        return false;
    return true;
  };
  static mt19937_64 rng(clock);
  uniform_int_distribution<ull> unif(1, p - 1);
  ull root;
  while(!test(root = unif(rng)));
  return root;
}