Adding iterative version of powMod.

1 files changed, 11 insertions, 0 deletions

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;
+}