diff options
Diffstat (limited to 'math')
| -rw-r--r-- | math/math.tex | 26 | ||||
| -rw-r--r-- | math/millerRabin.cpp | 17 | ||||
| -rw-r--r-- | math/phi.cpp | 9 | ||||
| -rw-r--r-- | math/primes.cpp | 39 |
4 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); +} |