Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Discrete logarithm solver.
#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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment