diff options
| -rw-r--r-- | math/math.tex | 42 | ||||
| -rw-r--r-- | tcr.pdf | bin | 266167 -> 265664 bytes |
2 files changed, 21 insertions, 21 deletions
diff --git a/math/math.tex b/math/math.tex index 855cc0d..6c20be2 100644 --- a/math/math.tex +++ b/math/math.tex @@ -19,37 +19,28 @@ Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$.\newline \subsection{Mod-Exponent über $\mathbb{F}_p$} \lstinputlisting{math/modExp.cpp} -\subsection{LGS über $\mathbb{F}_p$} -\lstinputlisting{math/lgsFp.cpp} - -\subsection{LGS über $\mathbb{R}$} -\lstinputlisting{math/gauss.cpp} - \subsection{Chinesischer Restsatz} \begin{itemize} \item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden. \item Direkte Formel für zwei Kongruenzen $x \equiv a \mod n$, $x \equiv b \mod m$: - \[ - x \equiv a - y * n * \frac{a - b}{d} \mod \frac{mn}{d} - \qquad \text{mit} \qquad - d := ggT(n, m) = yn + zm - \] - Formel kann auch für nicht teilerfremde Moduli verwendet werden. - Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung, - wenn $a_i \equiv a_j \mod \gcd(m_i, m_j)$. In diesem Fall sind keine Faktoren - auf der linken Seite erlaubt. + \[ + x \equiv a - y * n * \frac{a - b}{d} \mod \frac{mn}{d} + \qquad \text{mit} \qquad + d := ggT(n, m) = yn + zm + \] + Formel kann auch für nicht teilerfremde Moduli verwendet werden. + Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung, + wenn $a_i \equiv a_j \mod \gcd(m_i, m_j)$. + In diesem Fall sind keine Faktoren + auf der linken Seite erlaubt. \end{itemize} \lstinputlisting{math/chineseRemainder.cpp} -\subsection{Primzahlsieb von \textsc{Eratosthenes}} -\lstinputlisting{math/primeSieve.cpp} - \subsection{Primzahltest \& Faktorisierung} \lstinputlisting{math/primes.cpp} -\subsection{Binomialkoeffizienten} -Vorberechnen, wenn häufig benötigt. -\lstinputlisting{math/binomial.cpp} +\subsection{Primzahlsieb von \textsc{Eratosthenes}} +\lstinputlisting{math/primeSieve.cpp} \subsection{\textsc{Euler}sche $\varphi$-Funktion} \begin{itemize}[nosep] @@ -91,6 +82,15 @@ Vorberechnen, wenn häufig benötigt. \subsection{Diskreter Logarithmus} \lstinputlisting{math/discreteLogarithm.cpp} +\subsection{Binomialkoeffizienten} +\lstinputlisting{math/binomial.cpp} + +\subsection{LGS über $\mathbb{F}_p$} +\lstinputlisting{math/lgsFp.cpp} + +\subsection{LGS über $\mathbb{R}$} +\lstinputlisting{math/gauss.cpp} + \subsection{Polynome \& FFT} Multipliziert Polynome $A$ und $B$. \begin{itemize}[nosep] Binary files differ |