Fshl0

Discrete Logarithm

Feb 21st, 2021
109
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int solve(int a, int b, int m) {
  2.     a %= m, b %= m;
  3.     int k = 1, add = 0, g;
  4.     while ((g = gcd(a, m)) > 1) {
  5.         if (b == k)
  6.             return add;
  7.         if (b % g)
  8.             return -1;
  9.         b /= g, m /= g, ++add;
  10.         k = (k * 1ll * a / g) % m;
  11.     }
  12.  
  13.     int n = sqrt(m) + 1;
  14.     int an = 1;
  15.     for (int i = 0; i < n; ++i)
  16.         an = (an * 1ll * a) % m;
  17.  
  18.     unordered_map<int, int> vals;
  19.     for (int q = 0, cur = b; q <= n; ++q) {
  20.         vals[cur] = q;
  21.         cur = (cur * 1ll * a) % m;
  22.     }
  23.  
  24.     for (int p = 1, cur = k; p <= n; ++p) {
  25.         cur = (cur * 1ll * an) % m;
  26.         if (vals.count(cur)) {
  27.             int ans = n * p - vals[cur] + add;
  28.             return ans;
  29.         }
  30.     }
  31.     return -1;
  32. }
RAW Paste Data