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/math.tex           |  2 ++
 math/modPowIterativ.cpp | 11 +++++++++++
 2 files changed, 13 insertions(+)
 create mode 100644 math/modPowIterativ.cpp

(limited to 'math')

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;
+}
-- 
cgit v1.2.3