Fast factorization method and Euler's phi function

5 files changed, 72 insertions, 19 deletions

diff --git a/math/math.tex b/math/math.tex
index 56e9fc1..ba94b18 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -44,13 +44,35 @@ Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$.\newline
 \subsection{Primzahlsieb von \textsc{Eratosthenes}}
 \lstinputlisting{math/primeSieve.cpp}
 
-\subsection{\textsc{Miller}-\textsc{Rabin}-Primzahltest}
-\lstinputlisting{math/millerRabin.cpp}
+\subsection{Primzahltest \& Faktorisierung}
+\lstinputlisting{math/primes.cpp}
 
 \subsection{Binomialkoeffizienten}
 Vorberechnen, wenn häufig benötigt.
 \lstinputlisting{math/binomial.cpp}
 
+\subsection{\textsc{Euler}sche $\varphi$-Funktion}
+\begin{itemize}[nosep]
+	\item Zählt die relativ primen Zahlen $\leq n$.
+
+	\item Multiplikativ:
+	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
+
+	\item $p$ prim, $k \in \mathbb{N}$:
+	$~\varphi(p^k) = p^k - p^{k - 1}$
+
+	\item $n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}$:
+	$~\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right)$
+	Evtl. ist es sinnvoll obgien Code zum Faktorisieren zu benutzen und dann diese Formel anzuwenden.
+
+	\item \textbf{\textsc{Euler}'s Theorem:}
+	Seien $a$ und $m$ teilerfremd. Dann:
+	$a^{\varphi(m)} \equiv 1 \mod m$\newline
+	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
+	$a^{m} \equiv a \mod m$
+\end{itemize}
+\lstinputlisting{math/phi.cpp}
+
 \subsection{Polynome \& FFT}
 Multipliziert Polynome $A$ und $B$.
 \begin{itemize}[nosep]
diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp
deleted file mode 100644
index fd856d1..0000000
--- a/math/millerRabin.cpp
+++ /dev/null
@@ -1,17 +0,0 @@
-// Laufzeit: O(log n). Exakt, nicht propabilistisch.
-bool isPrime(ll n) {
-	if(n == 2) return true;
-	if(n < 2 || n % 2 == 0) return false;
-	ll d = n - 1, j = 0;
-	while(d % 2 == 0) d >>= 1, j++;
-	for(int a = 2; a <= min((ll)37, n - 1); a++) {
-		ll v = powMod(a, d, n); // Implementierung von oben.
-		if(v == 1 || v == n - 1) continue;
-		for(int i = 1;  i <= j; i++) {
-			v = multMod(v, v, n); // Implementierung von oben.
-			if(v == n - 1 || v <= 1) break;
-		}
-		if(v != n - 1) return false;
-	}
-	return true;
-}
diff --git a/math/phi.cpp b/math/phi.cpp
new file mode 100644
index 0000000..c8f8900
--- /dev/null
+++ b/math/phi.cpp
@@ -0,0 +1,9 @@
+ll phi(ll n) {
+  ll result = n;
+  for(int i = 2; i * i <= n; ++i) if(n % i == 0) {
+    while(n % i == 0)n /= i;
+    result -= result / i;
+  }
+  if(n > 1) result -= result / n;
+  return result;
+}
diff --git a/math/primes.cpp b/math/primes.cpp
new file mode 100644
index 0000000..0065939
--- /dev/null
+++ b/math/primes.cpp
@@ -0,0 +1,39 @@
+bool isPrime(ll n) { // Miller Rabin Primzahltest. O(log n)
+	if(n == 2) return true;
+	if(n < 2 || n % 2 == 0) return false;
+	ll d = n - 1, j = 0;
+	while(d % 2 == 0) d >>= 1, j++;
+	for(int a = 2; a <= min((ll)37, n - 1); a++) {
+		ll v = powMod(a, d, n); // Implementierung von oben.
+		if(v == 1 || v == n - 1) continue;
+		for(int i = 1;  i <= j; i++) {
+			v = multMod(v, v, n); // Implementierung von oben.
+			if(v == n - 1 || v <= 1) break;
+		}
+		if(v != n - 1) return false;
+	}
+	return true;
+}
+
+ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim.
+  if (~n & 1) return 2;
+  ll c = rand() % n, x = rand() % n, y = x, d = 1;
+  while (d == 1) {
+    x = (multMod(x, x, n) + c) % n;
+    y = (multMod(y, y, n) + c) % n;
+    y = (multMod(y, y, n) + c) % n;
+    d = __gcd(abs(x - y), n);
+  }
+  return d == n ? rho(n) : d;
+}
+
+void factor(ll n, map<ll, int> &facts) {
+  if (n == 1) return;
+  if (isPrime(n)) {
+    facts[n]++;
+    return;
+  }
+  ll f = rho(n);
+  factor(n/f, facts);
+  factor(f, facts);
+}
diff --git a/tcr.pdf b/tcr.pdf
index 39a7702..9262782 100644
--- a/tcr.pdf
+++ b/tcr.pdf