ModLog

Returns the smallest x > 0 s.t. a^x = b pmod m, or -1 if no such x exists. modLog(a,1,m) can be used to calculate the order of a.

Time: O(sqrt m) 11 lines tested for all 0 <= a,x < 500 and 0 < m < 500.

content/number-theory/ModLog.h — Bjorn Martinsson, source: own work

ll modLog(ll a, ll b, ll m) {
	ll n = (ll) sqrt(m) + 1, e = 1, f = 1, j = 1;
	unordered_map<ll, ll> A;
	while (j <= n && (e = f = e * a % m) != b % m)
		A[e * b % m] = j++;
	if (e == b % m) return j;
	if (__gcd(m, e) == __gcd(m, b))
		rep(i,2,n+2) if (A.count(e = e * f % m))
			return n * i - A[e];
	return -1;
}