Fshl0

Discreet Root

Feb 22nd, 2021
111
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Finds the primitive root modulo p
  2. int generator(int p) {
  3.     vector<int> fact;
  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)
  9.                 n /= i;
  10.         }
  11.     }
  12.     if (n > 1)
  13.         fact.push_back(n);
  14.  
  15.     for (int res = 2; res <= p; ++res) {
  16.         bool ok = true;
  17.         for (int factor : fact) {
  18.             if (powmod(res, phi / factor, p) == 1) {
  19.                 ok = false;
  20.                 break;
  21.             }
  22.         }
  23.         if (ok) return res;
  24.     }
  25.     return -1;
  26. }
  27.  
  28. // This program finds all numbers x such that x^k = a (mod n)
  29. int main() {
  30.     int n, k, a;
  31.     scanf("%d %d %d", &n, &k, &a);
  32.     if (a == 0) {
  33.         puts("1\n0");
  34.         return 0;
  35.     }
  36.  
  37.     int g = generator(n);
  38.  
  39.     // Baby-step giant-step discrete logarithm algorithm
  40.     int sq = (int) sqrt (n + .0) + 1;
  41.     vector<pair<int, int>> dec(sq);
  42.     for (int i = 1; i <= sq; ++i)
  43.         dec[i-1] = {powmod(g, i * sq * k % (n - 1), n), i};
  44.     sort(dec.begin(), dec.end());
  45.     int any_ans = -1;
  46.     for (int i = 0; i < sq; ++i) {
  47.         int my = powmod(g, i * k % (n - 1), n) * a % n;
  48.         auto it = lower_bound(dec.begin(), dec.end(), make_pair(my, 0));
  49.         if (it != dec.end() && it->first == my) {
  50.             any_ans = it->second * sq - i;
  51.             break;
  52.         }
  53.     }
  54.     if (any_ans == -1) {
  55.         puts("0");
  56.         return 0;
  57.     }
  58.  
  59.     // Print all possible answers
  60.     int delta = (n-1) / gcd(k, n-1);
  61.     vector<int> ans;
  62.     for (int cur = any_ans % delta; cur < n-1; cur += delta)
  63.         ans.push_back(powmod(g, cur, n));
  64.     sort(ans.begin(), ans.end());
  65.     printf("%d\n", ans.size());
  66.     for (int answer : ans)
  67.         printf("%d ", answer);
  68. }
RAW Paste Data