From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/discreteLogarithm.cpp | 25 +++++++++++++------------ 1 file changed, 13 insertions(+), 12 deletions(-) (limited to 'math/discreteLogarithm.cpp') diff --git a/math/discreteLogarithm.cpp b/math/discreteLogarithm.cpp index 6d3f656..d9227b9 100644 --- a/math/discreteLogarithm.cpp +++ b/math/discreteLogarithm.cpp @@ -1,13 +1,14 @@ -// Bestimmt Lösung x für a^x=b mod m. -ll solve (ll a, ll b, ll m) { // Laufzeit: O(sqrt(m)*log(m)) - ll n = (ll)sqrt((double)m) + 1; - map vals; - for (int i = n; i >= 1; i--) vals[powMod(a, i * n, m)] = i; - for (int i = 0; i <= n; i++) { - ll cur = (powMod(a, i, m) * b) % m; - if (vals.count(cur)) { - ll ans = vals[cur] * n - i; - if (ans < m) return ans; - }} - return -1; +ll dlog(ll a, ll b, ll m) { + ll bound = sqrtl(m) + 1; //memory usage bound + map vals; + for (ll i = 0, e = 1; i < bound; i++, e = (e * a) % m) { + vals[e] = i; + } + ll fact = powMod(a, m - bound - 1, m); + + for (ll i = 0; i < m; i += bound, b = (b * fact) % m) { + if (vals.count(b)) { + return i + vals[b]; + }} + return -1; } -- cgit v1.2.3