numbertheory.tex

a very popular packet of cryptography tools,it encloses the most common used algorithm and protocols

\newpage
\begin{center}
\fbox{\parbox{15cm}{
    \emph{Seneca\index{Seneca}\footnotemark:}\\
    Lang ist der Weg durch Lehren, kurz und wirksam durch Beispiele.
}}
\end{center}
\addtocounter{footnote}{0}
\footnotetext{Lucius Annaeus Seneca, philosophischer Schriftsteller und
              Dichter, 4~v.~Chr. $-$ 65~n.~Chr.}

% ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
% \pagebreak
\subsection{Beispiele f"ur modulares Rechnen}

Wir haben bisher gesehen:

F"ur zwei nat"urliche Zahlen $a$ und $m$ bezeichnet  $a$ mod $m$  den Rest, den man erh"alt, 
wenn man $a$ durch $m$ teilt. Daher ist $a {\rm ~(mod~ } m$) stets eine Zahl zwischen $0$ und $m-1$.

Zum Beispiel gilt: $1 \equiv  6  \equiv  41 {\rm ~(mod~ } 5)$, denn der Rest ist jeweils $1$.

Ein anderes Beispiel ist: $2000  \equiv  0 {\rm ~(mod~ } 4)$, denn $4$ geht in $2000$ ohne Rest auf.

In der modularen Arithmetik gibt es nur eine eingeschr"ankte Menge
nicht-negativer Zahlen. Deren Anzahl wird durch einen Modul $m$ vorgegeben.
Ist der Modul $m = 5$, werden nur die 5 Zahlen der Menge $\{ 0, 1, 2, 3, 4\}$ benutzt.

Ein Rechenergebnis gr"o"ser als $4$ wird dann \glqq modulo'' $5$ umgeformt, d.h. es ist
der Rest, der sich bei der Division des Ergebnisses durch $5$ ergibt. So ist
etwa $2*4 \equiv 8 \equiv 3 {\rm ~(mod~ } 5)$, da $3$ der Rest ist, wenn man $8$ durch $5$ teilt.


% --------------------------------------------------------------------------
\subsubsection{Addition und Multiplikation} \index{Addition} \index{Multiplikation}\label{addmult}

Im folgenden werden 
\begin{itemize}
\item die Additionstabelle\footnote{%
Bemerkung zur Subtraktion modulo 5: \\
      $2 - 4 \equiv -2 \equiv 3{\rm ~mod~}5.$\\
      Es gilt modulo $5$ also nicht, dass $-2 = 2$ (siehe auch \hyperlink{Appendix_C}{Anhang C zu diesem Kapitel}). 
      } f"ur ${\rm mod~ } 5$ und
\item die Multiplikationstabellen\footnote{\label{ftn-mod6}%
Bemerkung zur Division modulo 6:\index{Division modulo $n$}

\noindent Bei der Division darf nicht durch die Null geteilt werden, dies liegt an
der besonderen Rolle der $0$ als Identit"at bei der Addition:\\
f"ur alle $a$ gilt $a*0=0, $ denn $a*0 = a*(0+0) =a*0 + a*0.$ Es ist
offensischtlich, dass $0$ keine Inverse bzgl. der Multiplikation besitzt,
denn sonst m"usste gelten $0 = 0 * 0^{-1} = 1.$ Vergleiche Fu"snote
\ref{ftn-res-divmodn}.  } f"ur mod $5$ und f"ur mod $6$
\end{itemize}
aufgestellt.

% --------------------------------------------------------------------------
\subsubsection*{Beispiel Additionstabelle:}
Das Ergebnis der Addition von $3$ und $4 {\rm ~(mod~ } 5)$ wird folgenderma"sen bestimmt:
berechne $3 + 4 = 7$ und ziehe solange die $5$ vom Ergebnis ab, bis sich ein
Ergebnis kleiner als der Modul ergibt: $7 - 5 = 2$. Also ist: $3 + 4 \equiv 2 {\rm ~(mod~ } 5)$.

\begin{table}[h]
\begin{center}
\begin{tabular}{r|ccccc}
Additionstabelle modulo 5: \quad + &  0 & 1 & 2 & 3 & 4  \\
\hline
0 &  0 & 1 & 2 & 3 & 4 \\  
1 & 1 &  2 & 3 & 4 & 0 \\
2 & 2 & 3 & 4 & 0 & 1 \\
3 & 3 & 4 & 0 & 1 & 2 \\
4 & 4 & 0 & 1 & 2 & 3 
\end{tabular} 
\end{center} 
\end{table}

% --------------------------------------------------------------------------
\subsubsection*{Beispiel Multiplikationstabelle:}
Das Ergebnis der Multiplikation $4 * 4 {\rm ~(mod~ } 5)$ wird folgenderma"sen berechnet: berechne $ 4*4=16$ und
ziehe solange die $5$ ab, bis sich ein Ergebnis kleiner als der Modul ergibt:
$$16 - 5 = 11;~ 11 - 5 = 6;~6- 5 = 1.$$
Direkt ergibt es sich auch aus der Tabelle: $4 * 4 \equiv 1 {\rm ~(mod~} 5)$, weil $16 : 5 = 3$ Rest $1$.
Die Multiplikation wird auf der Menge $\mathbb{Z}$ ohne $0$ definiert.

        
\begin{table}[h]
\begin{center}
\begin{tabular}{r|cccc}
Multiplikationstabelle modulo 5: \quad * & 1& 2 & 3 & 4  \\
\hline 
1 & 1 &    2    &    3    & 4 \\
2 & 2 & {\bf 4} & {\bf 1} & 3 \\ 
3 & 3 & {\bf 1} & {\bf 4} & 2  \\
4 & 4 &    3    &    2    & 1 
\end{tabular}
\end{center} 
\end{table}


% --------------------------------------------------------------------------
\newpage
\subsubsection{Additive und multiplikative Inversen} \label{multmodn} \index{Inverse!additive} \index{Inverse!multiplikative}

Aus den Tabellen kann man zu jeder Zahl die Inversen bez"uglich der Addition
und der Multiplikation ablesen.

Die Inverse einer Zahl ist diejenige Zahl, die bei Addition der beiden
Zahlen das Ergebnis $0$ und bei der Multiplikation das Ergebnis $1$ ergibt. So
ist die Inverse von $4$ f"ur die Addition mod $5$ die $1$ und f"ur die
Multiplikation mod $5$ die $4$ selbst, denn
\begin{alignat}{2}
4 + 1 &  =  & 5 & \equiv 0 {\rm ~(mod~ } 5); \nonumber \\
4 * 4 &  = & ~16 & \equiv 1 {\rm ~(mod~ } 5). \nonumber
\end{alignat}
Die Inverse von $1$ bei der Multiplikation mod $5$ ist $1$; die Inverse modulo $5$
von $2$ ist $3$ und weil die Multiplikation kommutativ ist, ist die Inverse von
$3$ wiederum die $2$.

Wenn man zu einer beliebigen Zahl (hier $2$) eine weitere beliebige Zahl (hier $4$) addiert bzw.
multipliziert und danach zum Zwischenergebnis ($1$ bzw. $3$)
die jeweilige Inverse der weiteren Zahl ($1$ bzw. $4$) 
addiert\footnote{%
Allgemein: $x + y + (-y) \equiv x{\rm ~(mod~}m)$ [$(-y)$ = additive Inverse zu $y{\rm ~(mod~}m)$]
} bzw. multipliziert,
ist das Gesamtergebnis gleich dem Ausgangswert.

{\bf Beispiele:}
\begin{eqnarray*}
2 + 4 \equiv 6 \equiv 1 {\rm ~(mod~ } 5) ; \quad 1 + 1 \equiv 2 \equiv 2 {\rm ~(mod~ } 5)  \nonumber \\
2 * 4 \equiv 8 \equiv 3 {\rm ~(mod~ } 5) ; \quad 3 * 4 \equiv 12 \equiv 2 {\rm ~(mod~ } 5) \nonumber
\end{eqnarray*}

In der Menge $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$ f"ur die Addition und in der Menge $\mathbb{Z}_5 \setminus \{ 0\}$  f"ur
die Multiplikation haben alle Zahlen eine {\bf eindeutige} Inverse
bez"uglich modulo $5$.

Bei der modularen Addition ist das f"ur jeden Modul (also nicht nur f"ur $5$)
so.

Bei der modularen Multiplikation dagegen ist das nicht so:
\begin{satz}\label{thm-zth-multinv}
F"ur eine nat"urliche Zahl $a$ aus der Menge $\{1, \cdots, m-1\}$ gibt es genau dann eine\index{ggT}
multiplikative Inverse, wenn sie mit dem Modul $m$ \index{teilerfremd}
teilerfremd\footnote{%
Es gilt: Zwei ganze Zahlen $a$ und $b$ sind genau dann teilerfremd, wenn ${\rm ggT}(a, b) = 1$.\\
Desweiteren gilt: Ist $p$ prim und $a$ eine beliebige ganze Zahl, die kein
Vielfaches von $p$ ist, so sind beide Zahlen teilerfremd.\\
Weitere Bezeichnungen zum Thema Teilerfremdheit (mit $a_i \in \mathbb{Z}, i=1, \cdots, n$):
\begin{enumerate}
\item $a_1,a_2, \cdots, a_n$ hei"sen {\em relativ prim} \index{relativ prim}, wenn $ {\rm~ggT}(a_1, \cdots , a_n) =1.$
\item F"ur mehr als $2$ Zahlen  ist eine noch st"arkere Anforderung:\\
      $a_1, \cdots , a_n$ hei"sen {\em paarweise relativ prim}, wenn f"ur alle $i=1, \cdots, n$ und 
      $j=1, \cdots , n$ mit $ i \neq j $ gilt: $ {\rm~ggT} (a_i, a_j) =1. $
\end{enumerate}
Beispiel: $2,3,6 $ sind relativ prim, da $ {\rm~ggT} (2,3,6)=1.$ 
Sie sind nicht paarweise prim, da $ {\rm~ggT} (2,6)=2>1.$
} ist, d.h. wenn $a$ und $m$ keine gemeinsamen Primfaktoren haben.
\end{satz}

Da $m=5$ eine Primzahl ist, sind die Zahlen $1$ bis $4$ teilerfremd zu $5$, und es
gibt mod $5$ zu {\bf jeder} dieser Zahlen eine multiplikative Inverse.

Ein Gegenbeispiel zeigt die Multiplikationstabelle f"ur mod $6$ (da der Modul $6$
nicht prim ist, sind nicht alle Elemente aus $\mathbb{Z}_6\setminus \{0\}$ zu $6$ teilerfremd):

\begin{table}[h]
\begin{center}
\begin{tabular}{r|ccccc}
Multiplikationstabelle modulo $6$: \quad* &  1 & 2 & 3 & 4 & 5  \\
\hline 
1 &  1 & 2 & 3 & 4 & 5 \\  
2 &  2 & {\bf 4} & {\bf 0} & {\bf 2} & 4 \\
3 &  3 & {\bf 0} & {\bf 3} & {\bf 0} & 3 \\
4 &  4 & {\bf 2} & {\bf 0} & {\bf 4} & 2 \\
5 &  5 & 4 & 3 & 2 & 1 \\
\end{tabular}  
\end{center} 
\end{table}


Neben der $0$ haben hier auch die Zahlen $2, 3$ und $4$ keine eindeutige Inverse
(man sagt auch, sie haben {\bf keine} Inverse, weil es die elementare Eigenschaft
einer Inversen ist, eindeutig zu sein).

Die Zahlen $2, 3$ und $4$ haben mit dem Modul $6$ den Faktor $2$ oder $3$ gemeinsam.
Nur die zu $6$ teilerfremden Zahlen $1$ und $5$ haben multiplikative Inverse, n"amlich jeweils sich selbst.

Die Anzahl der zum Modul $m$ teilerfremden Zahlen ist auch die Anzahl
derjenigen Zahlen, die eine multiplikative Inverse haben (vgl. unten die
\hyperlink{EulerFunction}{Euler-Funktion} \index{Eulersche Phi-Funktion} $J(m)$).

F"ur die beiden in den Multiplikationstabellen verwendeten Moduli $5$ und $6$
bedeutet dies:
Der Modul $5$ ist bereits eine Primzahl. Also gibt es in mod $5$ genau $J(5) = 5 - 1 = 4$ 
mit dem Modul teilerfremde Zahlen, also alle von $1$ bis $4$.

Da $6$ keine Primzahl ist, zerlegen wir $6$ in seine Faktoren: $6 = 2 * 3$.
Daher gibt es in mod $6$ genau $J(6) = (2-1)*(3-1) = 1 * 2 = 2$ Zahlen, die eine
multiplikative Inverse haben, n"amlich die $1$ und die $5$.

F"ur gro"se Moduli scheint es nicht einfach, die Tabelle der multiplikativen
Inversen zu berechnen (das gilt nur f"ur die in den oberen 
Multiplikationstabellen fett markierten Zahlen). Mit Hilfe des kleinen Satzes
von Fermat\index{Fermat!kleiner Satz} kann man daf"ur einen einfachen 
Algorithmus aufstellen \cite[S. 80]{Pfleeger1997}. Schnellere Algorithmen
werden z.B. in \cite{Knuth1998} \index{Euklidscher Algorithmus!erweiterter}
beschrieben\footnote{%
Mit dem erweiterten Satz von Euklid \index{ggT}(erweiterter ggT) kann man die
multiplikative Inverse berechnen und die Invertierbarkeit bestimmen (Siehe \hyperlink{Appendix_A}{Anhang A zu diesem Kapitel}).
Alternativ kann auch die Primitivwurzel genutzt werden. 
}.

\vskip +10 pt
Kryptographisch ist nicht nur die Eindeutigkeit der Inversen, sondern auch das
Aussch"opfen des gesamten Wertebereiches\index{Wertebereich} eine wichtige
Eigenschaft.

\begin{satz}\label{thm-zth-exhperm}
Sei $a,i\in \{1, \cdots , m-1\}$ mit ${\rm~ggT} (a,m)=1, $ dann nimmt f"ur
eine bestimmte Zahl $a$ das Produkt $a*i {\rm ~mod~} m$  alle Werte aus
$ \{1, \cdots ,m-1\}$ an (ersch"opfende Permutation\index{Permutation} der
L"ange $m-1$)\footnote{%
Vergleiche auch Satz \ref{thm-zth-ordp} in \hyperlink{Chapter_ElementaryNT_9}
{Kapitel \ref{MultOrdPrimitveRoot}, Multiplikative Ordnung und Primitivwurzel}.
}.
\end{satz}


Die folgenden drei Beispiele\footnote{%
In \hyperlink{AppArith1}{Anhang E zu diesem Kapitel} finden Sie den Quellcode zur Berechnung der Tabellen mit Mathematica\index{Mathematica}
und Pari-GP.\index{Pari-GP}
} veranschaulichen Eigenschaften der multiplikativen Inversen (hier sind nicht mehr 
die vollst"andigen Multiplikationstabellen angegeben, sondern nur die Zeilen f"ur die Faktoren $5$ und $6$).

\pagebreak
In der Multiplikationstabelle mod $17$ wurde f"ur $i = 1, 2, \cdots, 18$ berechnet:
\begin{itemize}
   \item[] $(5*i)/17 = a$ Rest $r$ und hervorgehoben $5*i \equiv 1$ (mod $17$),
   \item[] $(6*i)/17 = a$ Rest $r$ und hervorgehoben $6*i \equiv 1$ (mod $17$).
\end{itemize}
{\bf Gesucht} ist das $i$, f"ur das der Produktrest $ a*i$ modulo $17$ mit $a=5$ bzw. $a=6$
den Wert $1$ hat. 

{
\begin{table}[h] \label{SrcArith1a}
\subsubsection*{Tabelle 1: Multiplikationstabelle modulo $17$ (f"ur $a=5$ und $a=6$)}
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c||c|c|}
\hline 
i                   & 1  & 2  & 3  & 4  & 5  & 6  & 7  & 8  & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16  & 17 & 18 \\
\hline
\hline  
$5*i$                 & 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 & 75 & 80  & 85 & 90   \\
Rest                & 5 & 10 & 15  & 3  & 8 & 13  & {\bf 1}  & 6 & 11 & 16  & 4  & 9 & 14  & 2  & 7 & 12   & 0  & 5   \\
\hline
$6*i$                 & 6 & 12 & 18 & 24 & 30 & 36 & 42 & 48 & 54 & 60 & 66 & 72 & 78 & 84 & 90 & 96 & 102 & 108   \\
Rest                & 6 & 12  & {\bf 1}  & 7 & 13  & 2  & 8 & 14  & 3  & 9 & 15  & 4 & 10 & 16  & 5 & 11   & 0  & 6   \\
\hline
\end{tabular}
\end{center} 
\end{table}
}
\vskip - 12 pt
Da sowohl $5$ als auch $6$ jeweils teilerfremd\index{teilerfremd} zum Modul $m=17$ sind, kommen zwischen
$i=1, \cdots, m$ f"ur die Reste alle Werte zwischen $0, \cdots, m-1$ vor (vollst"andige $m$-Permutation\index{Permutation}).
% \enlargethispage{0.5cm}