Fshl0

Primitive Root

Feb 22nd, 2021
97
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int generator (int p) {
  2.     vector <int> fact;
  3.     // calculate phi if p is not prime
  4.     int phi = p - 1, n = phi;
  5.     for (int i = 2; i * i <= n; i++) {
  6.         if (n % i == 0) {
  7.             fact.push_back (i);
  8.             while (n % i == 0) n /= i;
  9.         }
  10.     }
  11.     if (n > 1) fact.push_back (n);
  12.     for (int res = 2; res <= p; res++) {
  13.         bool ok = true;
  14.         for (size_t i = 0; i < fact.size() && ok; i++)
  15.             ok &= pow_with_mod (res, phi / fact[i], p) != 1;
  16.         if (ok) return res;
  17.     }
  18.     return -1;
  19. }
RAW Paste Data