Discrete logarithm solver.

discrete_log.cc

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// This implementation uses cast to __int128 for products because
// of big input (0 < q < 5*10^10).

ll mpow(ll x, ll n, ll m)
{
    n %= m-1;
    x %= m;
    ll ans = 1;
    while (n > 0) {
        if (n & 1) ans = (__int128)ans * x % m;
        x = (__int128)x * x % m;
        n >>= 1;
    }
    return ans;
}

int main()
{
    ll g, h, q;
    cin >> g >> h >> q;
    ll k = 0;
    while (k*k < q) ++k;
    unordered_map<ll,ll> A;
    A.rehash(1e6);
    ll v = (__int128)mpow(g, (k-1)*(q-2), q) * h % q;
    for (ll a = k-1; a >= 0; --a) {
        A[v] = a;
        v = (__int128)v * g % q;
    }
    v = 1;
    ll g_k = mpow(g, k, q);
    for (ll b = 0; b <= k; ++b) {
        if (A.count(v)) {
            cout << A[v]+k*b << endl;
            break;
        }
        v = (__int128)v * g_k % q;
    }
}