LaTeX-examples/publications/facharbeit-rsa/Kapitel-6.tex

\section{Multiplikativ inverses Element}\label{sec:Multiplikativ-Inverses}
\subsection{Definition und Beispiele}
Das multiplikativ inverse Element $d$ von $e$ ergibt bei der
Multiplikation mit $e$ das neutrale Element der Multiplikation, also
die Eins: $d \cdot e = 1$

In $\mathbb{R} \setminus \Set{0}$ hat jedes Element ein multiplikativ
Inverses, den Kehrbruch. In $\mathbb{Z}/7 \mathbb{Z}$ ist das
multiplikativ Inverse von zwei in der Restgruppe von vier, da
$2 \cdot 4 = 8$ und $8 \equiv 1 \imod{7}$.
Mit dem erweitertem euklidischem Algorithmus kann man das
multiplikativ Inverse von $a$ in $\mathbb{Z}/n \mathbb{Z}$ finden.

\subsection{Erweiterter euklidischer Algorithmus}
Sind zwei Zahlen $a > b$ gegeben und will deren größten gemeinsamen
Teiler berechnen, so kann man den erweiterten euklidischen
Algorithmus anwenden:

\begin{enumerate}
    \item Größtmögliches $q$ wählen, so dass gilt $a = q_1 \cdot b + r_1$
    \item $b = q_2 \cdot r_1 + r_2$
    \item $r_1 = q_3 \cdot r_2 + r_3$
    \item \dots
    \item bis $r_{n-2} = q_n \cdot r_{n-1} + r_n$ mit $r_n = 0$
\end{enumerate}

Dann ist $r_{n-1} = ggT(a,b)$

Mit diesem Algorithmus kann man nun das multiplikativ Inverse von $a$
in $\mathbb{Z}/n \mathbb{Z}$ finden, wenn der größte gemeinsame Teiler von $a$ und
$n$ gleich 1 ist. Da im vorletzten Schritt $r_{n - 1} = 1$ ist, kann man 1 als
Linearkombination der Reste von $r_{n - 3}$ und $r_{n - 2}$
darstellen. Diese Reste kann man wiederum als Linearkombination
vorhergehender Reste darstellen. Dies setzt man so lange fort,
bis man eine Linearkombination mit $a$ und $n$ von 1 hat. Da wir im
Restklassenring $n$ sind, muss man nur das Produkt mit $a$ betrachten
und kann das multiplikativ Inverse zu $a$ im Restklassenring
$\mathbb{Z}/n \mathbb{Z}$ ablesen.


Hier ein Beispiel zur Veranschaulichung:

Sei $a = (\text{Primzahl}_1 - 1) \cdot (\text{Primzahl}_2 - 1) =(3 - 1) \cdot (47 - 1) = 92$ und $b=71$

Gesucht ist das multiplikativ Inverse $b \in \mathbb{Z} / a \mathbb{Z}$ von $x \cdot 71 \equiv 1 \imod{92}$:

\begin{tabular}{lll}
\textbf{Schritt 1}: euklidischer Algorithmus & & \textbf{Schritt 2}: nach Rest auflösen\\
$91=1 \cdot 71 + 21$ \myDownArrow & $\rightarrow$     & $21 = 92 - 71$ \myUpArrow\\
$71=3 \cdot 21 + 8$     & $\rightarrow$     & $8 = 71 - 3 \cdot 21$\\
$21=2 \cdot 8 + 5$      & $\rightarrow$     & $5 = 21 - 2 \cdot 8$\\
$ 8=1 \cdot 5 + 3$      & $\rightarrow$     & $3 =  8 - 1 \cdot 5$\\
$ 5=1 \cdot 3 + 2$      & $\rightarrow$     & $2 =  5 - 1 \cdot 3$\\
$ 3=1 \cdot 2 + 1$      & $\rightarrow$     & $1 =  3 - 1 \cdot 2$
\end{tabular}

\textbf{Schritt 3}: so lange Reste einsetzen, bis eine Linearkombination der Form
$1 = x \cdot 92 + y \cdot 71$ gefunden ist:

\begin{align*}
1 &= 3 - (5 - 3)                             &&= 2 \cdot 3 - 5 \\
1 &= 2 \cdot (8 - 5) - (21 - 2 \cdot 8)        &&= 4 \cdot 8 - 2 \cdot 5 - 21 \\
1 &= 4 \cdot 8 - 2 \cdot (21 - 2 \cdot 8) - 21  &&= 8 \cdot 8 - 3 \cdot 21 \\
1 &= 8 \cdot (71 - 3 \cdot 21) - 3 \cdot (92 - 71) &&= 11 \cdot 71 - 24 \cdot 21 - 3 \cdot 92 \\
1 &= 11 \cdot 71 - 3 \cdot 92 - 24 \cdot (92 - 71) &&= 35 \cdot 71 - 27 \cdot 92
\end{align*}

Das bedeutet 35 ist das multiplikativ Inverse zu 71 in
$ \mathbb{Z} / 92 \mathbb{Z}$ und erfüllt damit die Kongruenzgleichung
$35 \cdot 71 \equiv 1 \imod{92}$.

Zusätzlich hat man damit weitere multiplikativ Inverse gefunden:
\begin{itemize}
    \item $-27 \cdot 92 \equiv 1 \imod{71}$
    \item $-27 \cdot 92 \equiv 1 \imod{35}$
    \item $35 \cdot 71 \equiv 1 \imod{27}$
\end{itemize}