1 files changed, 17 insertions, 15 deletions

diff --git a/content/math/math.tex b/content/math/math.tex
index 4ac6c9e..fdf7081 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -26,7 +26,7 @@
 	\end{methods}

 	\sourcecode{math/permIndex.cpp}

 \end{algorithm}

-\clearpage

+\columnbreak

 

 \subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}

 %\vspace{-1.25em}

@@ -100,8 +100,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		wenn $a\equiv~b \bmod \ggT(m, n)$.

 		In diesem Fall sind keine Faktoren

 		auf der linken Seite erlaubt.

-	\end{itemize}

-	\sourcecode{math/chineseRemainder.cpp}

+ 	\end{itemize}

+ 	\sourcecode{math/chineseRemainder.cpp}

 \end{algorithm}

 

 \begin{algorithm}{Primzahltest \& Faktorisierung}

@@ -121,7 +121,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \begin{algorithm}{Matrix-Exponent}

 	\begin{methods}

 		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}

-		\method{calc}{berechnet $m^b\cdot$}{\log(b)\cdot n^2}

+		\method{calc}{berechnet $m^b \cdot v$}{\log(b)\cdot n^2}

 	\end{methods}

 	\textbf{Tipp:} wenn \code{v[x]=1} und \code{0} sonst, dann ist \code{res[y]} = $m^b_{y,x}$.

 	\sourcecode{math/matrixPower.cpp}

@@ -236,7 +236,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/legendre.cpp}

 \end{algorithm}

 

-\begin{algorithm}{Lineares Sieb und Multiplikative Funktionen}

+\begin{algorithm}{Lineares Sieb und multiplikative Funktionen}

 	Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.

 	

 	$\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen.

@@ -250,7 +250,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!

 	

 	\sourcecode{math/linearSieve.cpp}

-	\textbf{\textsc{Möbius}-Funktion:}

+	\textbf{\textsc{Möbius} Funktion:}

 	\begin{itemize}

 		\item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat

 		\item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat

@@ -263,7 +263,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		\item $p$ prim, $k \in \mathbb{N}$:

 		$~\varphi(p^k) = p^k - p^{k - 1}$

 		

-		\item \textbf{Euler's Theorem:}

+		\item \textbf{\textsc{Euler}'s Theorem:}

 		Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.

 		Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:

 		$a^{m} \equiv a \pmod{m}$

@@ -321,6 +321,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \end{algorithm}

 

 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}

+	\label{fft}

 	Multipliziert Polynome $A$ und $B$.

 	\begin{itemize}

 		\item $\deg(A \cdot B) = \deg(A) + \deg(B)$

@@ -328,14 +329,15 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		$\deg(A \cdot B) + 1$ haben.

 		Größe muss eine Zweierpotenz sein.

 		\item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))}

-		\item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$

+		\item \emph{or} Transform berechnet sum over subsets

+			$\rightarrow$ inverse für inclusion/exclusion

 	\end{itemize}

 	%\sourcecode{math/fft.cpp}

 	%\sourcecode{math/ntt.cpp}

 	\sourcecode{math/transforms/fft.cpp}

 	\sourcecode{math/transforms/ntt.cpp}

 	\sourcecode{math/transforms/bitwiseTransforms.cpp}

-	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)

+	Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!)

 	\sourcecode{math/transforms/fftMul.cpp}

 \end{algorithm}

 

@@ -345,7 +347,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 

 \subsection{Kombinatorik}

 

-\paragraph{Wilsons Theorem}

+\paragraph{\textsc{Wilson}'s Theorem}

 A number $n$ is prime if and only if

 $(n-1)!\equiv -1\bmod{n}$.\\

 ($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$)

@@ -357,14 +359,14 @@ $(n-1)!\equiv -1\bmod{n}$.\\
 	\end{cases}

 \end{align*}

 

-\paragraph{\textsc{Zeckendorfs} Theorem}

+\paragraph{\textsc{Zeckendorf}'s Theorem}

 Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer

 verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei

 aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\

 \emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch

 hineinpasst.

 

-\paragraph{\textsc{Lucas}-Theorem}

+\paragraph{\textsc{Lucas}'s Theorem}

 Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung),

 so gilt

 \vspace{-0.75\baselineskip}

@@ -542,10 +544,10 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 \input{math/tables/series}

 

 \subsection{Wichtige Zahlen}

-\input{math/tables/composite}

+\input{math/tables/prime-composite}

 

-\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }

-\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}

+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }

+\method{recover}{findet $x$ und $y$ für $c=x\*y^{-1}\bmod m$}{\log(m)}

 \textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!

 \sourcecode{math/recover.cpp}