6 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;
 }