blob: 973103af693c3bfe3e64c2e3b191215caec22118 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
\section{Mathe}
\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
\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$
\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}
\subsection{Primzahlsieb von Eratosthenes}
\lstinputlisting{math/primeSieve.cpp}
|
