From 463e389ea499dcc26314196c014a85ee9b124847 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sat, 15 Oct 2016 23:30:44 +0200
Subject: Adding primitive root and discrete logarithm.

---
 math/discreteLogarithm.cpp | 13 +++++++++++++
 1 file changed, 13 insertions(+)
 create mode 100644 math/discreteLogarithm.cpp

(limited to 'math/discreteLogarithm.cpp')

diff --git a/math/discreteLogarithm.cpp b/math/discreteLogarithm.cpp
new file mode 100644
index 0000000..6d3f656
--- /dev/null
+++ b/math/discreteLogarithm.cpp
@@ -0,0 +1,13 @@
+// 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<ll,ll> 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;
+}
-- 
cgit v1.2.3