Adding iterative version of powMod.

2 files changed, 13 insertions, 0 deletions

diff --git a/math/math.tex b/math/math.tex
index c2f5d63..c02d352 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -25,6 +25,8 @@ Sei $0 \leq x < n$. Definiere $d := \ggT(x, n)$.\newline
 
 \subsection{Mod-Exponent über $\mathbb{F}_p$}
 \lstinputlisting{math/modExp.cpp}
+Iterativ:
+\lstinputlisting{math/modPowIterativ.cpp}
 
 \subsection{Chinesischer Restsatz}
 \begin{itemize}
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;
+}