From 46b25f88e862a320db09e4d964bc9326ab37af78 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Mon, 26 Jun 2017 10:10:25 +0200
Subject: Adding iterative version of powMod.

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

(limited to 'math/modPowIterativ.cpp')

diff --git a/math/modPowIterativ.cpp b/math/modPowIterativ.cpp
new file mode 100644
index 0000000..f06b4bd
--- /dev/null
+++ b/math/modPowIterativ.cpp
@@ -0,0 +1,11 @@
+// Laufzeit: O(log (b))
+ll powMod(ll a, ll b, ll n) {
+  if (b == 0) return 1;
+  ll res = 1;
+  while (b > 1) {
+    if (b & 1) res = (a * res) % n;
+    a = (a * a) % n;
+    b /= 2;
+  }
+  return (a * res) % n;
+}
-- 
cgit v1.2.3