6 files changed, 120 insertions, 1 deletions
diff --git a/math/factor.cpp b/math/factor.cpp
new file mode 100644
index 0000000..43aeae3
--- /dev/null
+++ b/math/factor.cpp
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+typedef unsigned long long ll;
+
+const ll PRIME_SIZE = 10000000;
+vector<int> primes;
+
+//Call before calculating anything
+void primeSieve() {
+	vector<int> isPrime(PRIME_SIZE,true);
+	for(ll i = 2; i < PRIME_SIZE; i+=2) {
+		if(isPrime[i]) {
+			primes.push_back(i);
+			if(i*i <= PRIME_SIZE) {
+				for(ll j = i; i*j < PRIME_SIZE; j+=2) isPrime[i*j] = false;
+			}
+		}
+		if(i == 2)
+			i--;
+	}
+} 
+
+//Factorize the number n
+vector<int> factorize(ll n) {
+	vector<int> factor;
+	ll num = n;
+	int pos = 0;
+	while(num != 1)  {
+		if(num % primes[pos] == 0) {
+			num /= primes[pos];
+			factor.push_back(primes[pos]);
+		}
+		else
+			pos++;
+		if(primes[pos]*primes[pos] > n)
+			break;
+	}
+	if(num != 1)
+		factor.push_back(num);
+	return factor;
+	
+}
diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp
new file mode 100644
index 0000000..e42e4ab
--- /dev/null
+++ b/math/lgsFp.cpp
@@ -0,0 +1,27 @@
+void normalLine(ll n, ll line, ll p) { //normalisiert Zeile line
+	ll factor = multInv(mat[line][line], p); //Implementierung von oben
+	for (ll 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++) {
+		if (i == line) continue;
+		ll diff = mat[i][line]; //abziehen
+		for (ll j = 0; j <= n; j++) {
+			mat[i][j] -= (diff * mat[line][j]) % p;
+			while (mat[i][j] < 0) {
+				mat[i][j] += p;
+			}
+		}
+	}
+}
+
+void gauss(ll n, ll p) { //n x n+1-Matrix, Koerper F_p
+	for (ll line = 0; line < n; line++) {
+		normalLine(n, line, p);
+		takeAll(n, line, p);
+	}
+}
+\ No newline at end of file
diff --git a/math/math.tex b/math/math.tex
index f82ab65..973103a 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -15,6 +15,19 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 	\end{itemize}
 	\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
 \end{description}
+\lstinputlisting{math/multInv.cpp}
+
+\subsubsection{Faktorisierung}
+\lstinputlisting{math/factor.cpp}
+
+\subsubsection{Mod-Exponent über $\mathbb{F}_p$}
+\lstinputlisting{math/modExp.cpp}
+
+\subsection{LGS über $\mathbb{F}_p$}
+\lstinputlisting{math/lgsFp.cpp}
 
 \subsection{Binomialkoeffizienten}
-\lstinputlisting{math/binomial.cpp}
-\ No newline at end of file
+\lstinputlisting{math/binomial.cpp}
+
+\subsection{Primzahlsieb von Eratosthenes}
+\lstinputlisting{math/primeSieve.cpp}
diff --git a/math/modExp.cpp b/math/modExp.cpp
new file mode 100644
index 0000000..f738268
--- /dev/null
+++ b/math/modExp.cpp
@@ -0,0 +1,7 @@
+ll modPow(ll b, ll e, ll p) {
+	if (e == 0) return 1;
+	if (e == 1) return b;
+	ll half = modPow(b, e / 2, p), res = (half * half) % p;
+	if (e & 1) res *= b; res %= p;
+	return res;
+}
+\ No newline at end of file
diff --git a/math/multInv.cpp b/math/multInv.cpp
new file mode 100644
index 0000000..f9db815
--- /dev/null
+++ b/math/multInv.cpp
@@ -0,0 +1,5 @@
+ll multInv(ll n, ll p) { //berechnet das multiplikative Inverse von n in F_p
+	extendedEuclid(n, p); //implementierung von oben
+	x += ((x / p) + 1) * p;
+	return x % p;
+}
+\ No newline at end of file
diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
new file mode 100644
index 0000000..4c82bbe
--- /dev/null
+++ b/math/primeSieve.cpp
@@ -0,0 +1,22 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+typedef unsigned long long ll;
+
+vector<int> primeSieve(ll n) {
+	vector<int> primes;
+	vector<int> isPrime(n,true);
+	for(ll i = 2; i < n; i+=2) {
+		if(isPrime[i]) {
+			primes.push_back(i);
+			if(i*i <= n) {
+				for(ll j = i; i*j < n; j+=2) isPrime[i*j] = false;
+			}
+		}
+		if(i == 2)
+			i--;
+	}
+	return primes;
+}