diff options
| -rw-r--r-- | math/extendedEuclid.cpp | 15 | ||||
| -rw-r--r-- | math/gcd-lcm.cpp | 9 | ||||
| -rw-r--r-- | math/lgsFp.cpp | 36 | ||||
| -rw-r--r-- | math/math.tex | 20 | ||||
| -rw-r--r-- | math/modExp.cpp | 14 | ||||
| -rw-r--r-- | math/multInv.cpp | 5 | ||||
| -rw-r--r-- | tcr.pdf | bin | 255864 -> 255640 bytes |
7 files changed, 44 insertions, 55 deletions
diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp index 65d6ed9..66a6d93 100644 --- a/math/extendedEuclid.cpp +++ b/math/extendedEuclid.cpp @@ -1,11 +1,6 @@ -// Accepted in Aufgabe mit Forderung: |X|+|Y| minimal (primaer) und X<=Y (sekundaer). -// Hab aber keinen Beweis dafuer :) -ll x, y, d; // a * x + b * y = d = ggT(a,b) -void extendedEuclid(ll a, ll b) { - if (!b) { - x = 1; y = 0; d = a; return; - } - extendedEuclid(b, a % b); - ll x1 = y; ll y1 = x - (a / b) * y; - x = x1; y = y1; +ll extendedEuclid(ll a, ll b, ll &x, ll &y) { // a*x + b*y = ggt(a, b). + if (a == 0) { x = 0; y = 1; return b; } + ll x1, y1, d = extendedEuclid(b % a, a, x1, y1); + x = y1 - (b / a) * x1; y = x1; + return d; } diff --git a/math/gcd-lcm.cpp b/math/gcd-lcm.cpp index 10ecb3d..10198ac 100644 --- a/math/gcd-lcm.cpp +++ b/math/gcd-lcm.cpp @@ -1,8 +1,3 @@ // Laufzeiten: O(log(a) + log(b)) -ll gcd(ll a, ll b) { - return b == 0 ? a : gcd (b, a % b); -} - -ll lcm(ll a, ll b) { - return a * (b / gcd(a, b)); // Klammern gegen Overflow. -} +ll gcd(ll a, ll b) { return b == 0 ? a : gcd (b, a % b); } +ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); } diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp index 439e5b7..14549b7 100644 --- a/math/lgsFp.cpp +++ b/math/lgsFp.cpp @@ -1,28 +1,30 @@ // Laufzeit: O(n^3) -void normalLine(ll n, ll line, ll p) { // Normalisiert Zeile line. +void swapLines(int n, int l1, int l2) { + for (int i = 0; i <= n; i++) swap(mat[l1][i], mat[l2][i]); +} + +void normalLine(int n, int line, ll p) { ll factor = multInv(mat[line][line], p); // Implementierung von oben. - for (ll i = 0; i <= n; i++) { + for (int i = 0; i <= n; i++) { mat[line][i] *= factor; mat[line][i] %= p; - } -} +}} -void takeAll(ll n, ll line, ll p) { // Zieht Vielfaches von line von allen anderen Zeilen ab. - for (ll i = 0; i < n; i++) { +void takeAll(int n, int line, ll p) { + for (int i = 0; i < n; i++) { if (i == line) continue; ll diff = mat[i][line]; - for (ll j = 0; j <= n; j++) { + for (int j = 0; j <= n; j++) { mat[i][j] -= (diff * mat[line][j]) % p; - while (mat[i][j] < 0) { - mat[i][j] += p; - } - } - } -} + mat[i][j] %= p; + if (mat[i][j] < 0) mat[i][j] += p; +}}} -void gauss(ll n, ll p) { // nx(n+1)-Matrix, Koerper F_p. - for (ll line = 0; line < n; line++) { +void gauss(int n, ll p) { // nx(n+1)-Matrix, Körper F_p. + for (int line = 0; line < n; line++) { + int swappee = line; + while (mat[swappee][line] == 0) swappee++; + swapLines(n, line, swappee); normalLine(n, line, p); takeAll(n, line, p); - } -} +}} diff --git a/math/math.tex b/math/math.tex index b0ff8da..7d36c00 100644 --- a/math/math.tex +++ b/math/math.tex @@ -4,18 +4,16 @@ \lstinputlisting{math/gcd-lcm.cpp} \lstinputlisting{math/extendedEuclid.cpp} -\subsubsection{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$} -Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$. -\begin{description} - \item[Falls $d = 1$:] ~ - \begin{itemize}[nosep] - \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit - $\alpha x + \beta n = 1$. - \item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$. - \item $x^{-1} :\equiv \alpha \mod n$ +\paragraph{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$} +Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$.\newline +\textbf{Falls $d = 1$:} +\begin{itemize}[nosep] + \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit + $\alpha x + \beta n = 1$. + \item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$. + \item $x^{-1} :\equiv \alpha \mod n$ \end{itemize} - \item[Falls $d \neq 1$:] Es existiert kein $x^{-1}$. -\end{description} +\textbf{Falls $d \neq 1$:} Es existiert kein $x^{-1}$. \lstinputlisting{math/multInv.cpp} \subsection{Mod-Exponent über $\mathbb{F}_p$} diff --git a/math/modExp.cpp b/math/modExp.cpp index cd0f982..967068c 100644 --- a/math/modExp.cpp +++ b/math/modExp.cpp @@ -1,17 +1,15 @@ // Laufzeit: O(log(b)) -ll mult_mod(ll a, ll b, ll n) { +ll multMod(ll a, ll b, ll n) { if(a == 0 || b == 0) return 0; if(b == 1) return a % n; - - if(b % 2 == 1) return (a + mult_mod(a, b-1, n)) % n; - else return mult_mod((a + a) % n, b / 2, n); + if(b % 2 == 1) return (a + multMod(a, b-1, n)) % n; + else return multMod((a + a) % n, b / 2, n); } // Laufzeit: O(log(b)) -ll pow_mod(ll a, ll b, ll n) { +ll powMod(ll a, ll b, ll n) { if(b == 0) return 1; if(b == 1) return a % n; - - if(b % 2 == 1) return mult_mod(pow_mod(a, b-1, n), a, n); - else return pow_mod(mult_mod(a, a, n), b / 2, n); + if(b % 2 == 1) return multMod(powMod(a, b-1, n), a, n); + else return powMod(multMod(a, a, n), b / 2, n); } diff --git a/math/multInv.cpp b/math/multInv.cpp index 858e47c..2aedcd6 100644 --- a/math/multInv.cpp +++ b/math/multInv.cpp @@ -1,6 +1,7 @@ // Laufzeit: O(log (n) + log(p)) -ll multInv(ll n, ll p) { // Berechnet das multiplikative Inverse von n in F_p. - extendedEuclid(n, p); // Implementierung von oben. +ll multInv(ll n, ll p) { + ll x, y; + extendedEuclid(n, p, x, y); // Implementierung von oben. x += ((x / p) + 1) * p; return x % p; } Binary files differ |