Fshl0

Discrete Logarithm II

Feb 21st, 2021 (edited)
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ll DiscreteLogarithm (ll a, ll b, ll mod) {
  2.     a %= mod, b %= mod;
  3.     if (b == 1) return 0;
  4.     int cnt = 0; ll t = 1, g;
  5.     while ((g = __gcd (a, mod)) != 1) {
  6.         if (b % g) return -1;
  7.         mod /= g, b /= g;
  8.         t = t * a / g % mod;
  9.         cnt++;
  10.         if (t == b) return cnt;
  11.     }
  12.     unordered_map <ll, ll> mp;
  13.     int m = ceil (sqrt (1.0 * mod));
  14.     ll e = 1;
  15.     for (int i = 0; i < m; i++) {
  16.         mp[e * b % mod] = i;
  17.         e = e * a % mod;
  18.     }
  19.     ll nw = t;
  20.     for (int i = 1; i <= m + 1; i++) {
  21.         nw = e * nw % mod;
  22.         if (mp.count(nw)) {
  23.             return i * m - mp[nw] + cnt;
  24.         }
  25.     }
  26.     return -1;
  27. }
RAW Paste Data