📄 numbertheory.tex
字号:
{
{\bf Die multiplikative Inverse von $5$ (mod $17$) ist $7$, die Inverse von $6$ (mod $17$) ist $3$.}
\vskip +20 pt
\begin{table}[h] \label{SrcArith1b}
\subsubsection*{Tabelle 2: Multiplikationstabelle modulo $13$ (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 & 2 & 7 & 12 & 4 & 9 & {\bf 1} & 6 & 11 & 3 & 8 & 0 & 5 & 10 & 2 & 7 & 12 \\
\hline
$6*i$ & 6 & 12 & 18 & 24 & 30 & 36 & 42 & 48 & 54 & 60 & 66 & 72 & 78 & 84 & 90 & 96 & 102 & 108 \\
Rest & 6 & 12 & 5 & 11 & 4 & 10 & 3 & 9 & 2 & 8 & {\bf 1} & 7 & 0 & 6 & 12 & 5 & 11 & 4 \\
\hline
\end{tabular}
\end{center}
\end{table}
}
\vskip -12 pt
Da sowohl $5$ als auch $6$ auch zum Modul $m=13$ jeweils teilerfremd sind, kommen
zwischen $i=1, \cdots, m$ f"ur die Reste alle Werte zwischen $0, \cdots, m-1$ vor.
{\bf Die multiplikative Inverse von $5$ (mod $13$) ist $8$, die Inverse von $6$ (mod $13$) ist $11$.}
\vskip +15 pt
\pagebreak
Die folgende Tabelle enth"alt ein Beispiel daf"ur, wo der Modul $m$ und die Zahl $(a=6)$
{\em nicht} teilerfremd sind.
\vskip +15 pt
\begin{table}[h]
\subsubsection*{Tabelle 3: Multiplikationstabelle modulo $12$ (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 & 3 & 8 & {\bf 1} & 6 & 11 & 4 & 9 & 2 & 7 & 0 & 5 & 10 & 3 & 8 & 1 & 6 \\
\hline
6*i & 6 & 12 & 18 & 24 & 30 & 36 & 42 & 48 & 54 & 60 & 66 & 72 & 78 & 84 & 90 & 96 & 102 & 108 \\
Rest & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 \\
\hline
\end{tabular}
\end{center}
\end{table}
\vskip -12 pt
Berechnet wurde $(5 * i)$ (mod $12$) und $(6*i)$ (mod $12$).
Da $6$ und der Modul $m=12$ nicht teilerfremd\index{teilerfremd} sind, kommen zwischen $i=1, \cdots, m$
nicht alle Werte zwischen $0, \cdots, m-1$ vor und $6$ hat mod $12$ auch keine
Inverse!
\index{Inverse!additive} \index{Inverse!multiplikative}
{\bf Die multiplikative Inverse von $5$ (mod $12$) ist $5$. Die Zahl $6$ hat keine Inverse (mod $12$). }
% --------------------------------------------------------------------------
\subsubsection{Potenzieren}
\index{Potenzieren} Das Potenzieren ist in der modularen Arithmetik definiert als wiederholtes
Multiplizieren -- wie "ublich, nur dass jetzt Multiplizieren etwas anderes ist.
Es gelten mit kleinen Einschr"ankungen die "ublichen Rechenregeln wie
\begin{eqnarray*}
a^{b+c} & = & a^b * a^c, \nonumber \\
(a^b)^c & = & a^{b*c} = a^{c*b} = (a^c)^b. \nonumber
\end{eqnarray*}
Analog der modularen Addition und der modularen Multiplikation funktioniert
das modulare Potenzieren:
$$ 3^2 \equiv 9 \equiv 4 {\rm ~(mod~} 5). $$
Auch aufeinanderfolgendes Potenzieren geht analog:
{\bf Beispiel 1:}
\begin{quote}
$$ (4^3)^2 \equiv 64^2 \equiv 4096 \equiv 1 {\rm ~(mod~} 5). $$
(1) Reduziert man bereits {\bf Zwischenergebnisse} modulo $5$, kann man
schneller\footnote{%
Die Rechenzeit der Multiplikation zweier Zahlen h"angt normalerweise von der
L"ange der Zahlen ab. Dies sieht man, wenn man nach der Schulmethode z.B.
$474*228$ berechnet: Der Aufwand steigt quadratisch, da $3*3$ Ziffern
multipliziert werden m"ussen. Durch die Reduktion der Zwischenergebnisse
werden die Zahlen deutlich kleiner.
} rechnen, muss aber auch aufpassen, da sich dann nicht immer alles wie in der
gew"ohnlichen Arithmetik verh"alt.
\begin{eqnarray*}
(4^3)^2 & \equiv & (4^3{\rm ~(mod~}5))^2{\rm ~(mod~}5) \nonumber \\
& \equiv & (64{\rm ~(mod~}5))^2\;{\rm ~(mod~}5) \nonumber \\
& \equiv & 4^2{\rm ~(mod~}5) \nonumber \\
& \equiv & 16 \equiv 1 {\rm ~(mod~}5). \nonumber
\end{eqnarray*}
(2) Aufeinanderfolgende Potenzierungen lassen sich in der gew"ohnlichen
Arithmetik auf eine einfache Potenzierung zur"uckf"uhren, indem man die
Exponenten miteinander multipliziert:
$$ (4^3)^2 = 4^{3*2} = 4^6 = 4096. $$
In der modularen Arithmetik geht das nicht ganz so einfach, denn man erhielte:
$$ (4^3)^2 \equiv 4^{3*2{\rm ~(mod~}5)} \equiv 4^{6{\rm ~(mod~}5)} \equiv 4^1 \equiv 4{\rm ~(mod~}5). $$
Wie wir oben sahen, ist das richtige Ergebnis aber $1$ !!
(3) Deshalb ist f"ur das fortgesetzte Potenzieren in der modularen Arithmetik
die Regel etwas anders: man multipliziert die Exponenten nicht in (mod $m$),
sondern in (mod $J(m)$).
Mit $J(5) = 4$ ergibt sich:
$$
(4^3)^2 \equiv 4^{3\:*\:2{\rm ~(mod~}J(5))} \equiv 4^{6{\rm ~mod~}4} \equiv 4^2 \equiv 16 \equiv 1 {\rm ~(mod~}5).
$$
Das liefert das richtige Ergebnis.
\end{quote}
\vskip + 10 pt
\begin{satz}\label{thm-zth-pot}
$(a^b)^c \equiv a^{b*c{\rm ~(mod~}J(m))}{\rm ~(mod~}m)$.
\end{satz}
{\bf Beispiel 2:}
$$
3^{28} \equiv 3^{4\:*\:7} \equiv 3^{4\:*\:7{\rm ~(mod~}10)} \equiv 3^8 \equiv 6561 \equiv 5 {\rm ~(mod~}11).
$$
% --------------------------------------------------------------------------
\vskip + 10pt
\subsubsection{Schnelles Berechnen hoher Potenzen}
%\subsubsection*{3.6.3.1 ~~~Schnelles Berechnen hoher Potenzen}
%\addcontentsline{toc}{subsubsection}{~~~~~~~~~~3.6.3.1 ~Schnelles Berechnen hoher Potenzen}
\hypertarget{hohpot}{}\label{hohpot} \index{Potenz}
Bei RSA-Ver- und Entschl"usselungen\footnote{%
Siehe Kapitel \ref{rsabeweis} (Beweis des RSA-Verfahrens mit Euler-Fermat) und
Kapitel \ref{rsakonkret} (Das RSA-Verfahren mit konkreten Zahlen).
} m"ussen hohe Potenzen modulo $m$ berechnet werden. Schon die Berechnung $(100^5)
{\rm ~mod~}3$ sprengt den $32$ Bit langen \index{Long-Integer}
Long-Integer-Zahlenbereich, sofern man zur Berechnung von $a^n$ getreu der
Definition $a$ tats"achlich $n$-mal mit sich selbst multipliziert. Bei sehr gro"sen Zahlen w"are selbst ein
schneller Computerchip mit einer einzigen Exponentiation l"anger besch"aftigt
als das Weltall existiert. Gl"ucklicherweise gibt es f"ur die Exponentiation
(nicht aber f"ur das Logarithmieren) eine sehr wirksame Abk"urzung.
Wird der Ausdruck anhand der Rechenregeln der modularen Arithmetik anders
aufgeteilt, sprengt die Berechnung nicht einmal den $16$ Bit langen
Short-Integer-Bereich:\index{Short-Integer}
$$
(a^5) \equiv (((a^2{\rm ~(mod~}m))^2 {\rm ~(mod~}m)) * a){\rm ~(mod~}m).
$$
Dies kann man verallgemeinern, indem man den Exponenten bin"ar darstellt.
Beispielsweise w"urde die Berechnung von $a^n$ f"ur $n = 37$ auf dem naiven Wege $36$
Multiplikationen erfordern.
Schreibt man jedoch $n$ in der Bin"ardarstellung als $100101 = 1*2^5 + 1*2^2 + 1*2^0$,
so kann man umformen: $a^{37} = a^{2^5 + 2^2 + 2^0} = a^{2^5} * a^{2^2} * a^1$.
{\bf Beispiel 3:} $87^{43}{\rm ~(mod~}103)$. \\
Da $43 = 32+8+2+1$, $103$ prim , $43<J(103)$ ist und
die Quadrate (mod $103$) vorab berechnet werden k"onnen \\
\begin{eqnarray*}
87^2 & \equiv & 50 {\rm ~(mod~}103),\\
87^4 & \equiv & 50^2 \equiv 28 {\rm ~(mod~}103), \\
87^8 & \equiv & 28^2 \equiv 63 {\rm ~(mod~}103), \\
87^{16} & \equiv & 63^2 \equiv 55 {\rm ~(mod~}103),\\
87^{32} & \equiv & 55^2 \equiv 38 {\rm ~(mod~}103),
\end{eqnarray*}
gilt\footnote{%
In \hyperlink{AppArith2}{Appendix D} finden Sie den Beispielcode zum Nachrechnen der Square-and-Multiply Methode
mit Mathematica und Pari-GP.
}: \label{SrcArith2}
\begin{eqnarray*}
87^{43} & \equiv & 87^{32+8+2+1}{\rm ~(mod~}103) \nonumber \\
& \equiv & 87^{32} * 87^8 * 87^2 * 87 {\rm ~(mod~}103) \nonumber \\
& \equiv & 38 * 63 * 50 * 87 \equiv 85 {\rm ~(mod~}103). \nonumber
\end{eqnarray*}
Die Potenzen $(a^2)^k$ sind durch fortgesetztes Quadrieren leicht zu bestimmen.
Solange sich $a$ nicht "andert, kann ein Computer sie vorab berechnen und --
bei ausreichend Speicherplatz -- abspeichern. Um dann im Einzelfall $a^n$ zu
finden, muss er nur noch genau diejenigen $(a^2)^k$ miteinander multiplizieren,
f"ur die an der $k$-ten Stelle der Bin"ardarstellung von n eine Eins steht. Der
typische Aufwand f"ur $n=600$ sinkt dadurch von $2^{600}$ auf $2*600$ Multiplikationen!
Dieser h"aufig verwendete Algorithmus hei"st \glqq Square and Multiply''. \index{Square and multiply}
% --------------------------------------------------------------------------
\vskip +40 pt
\subsubsection{Wurzeln und Logarithmen} \index{Wurzel}
Die Umkehrungen des Potenzierens sind ebenfalls definiert: Wurzeln und
Logarithmen sind abermals ganze Zahlen, aber im Gegensatz zur "ublichen
Situation sind sie nicht nur m"uhsam, sondern bei sehr gro"sen Zahlen in
\glqq ertr"aglicher\grqq~ Zeit "uberhaupt nicht zu berechnen.
Gegeben sei die Gleichung: $a \equiv b^c{\rm ~(mod~}m)$.
\begin{itemize}
\item [\bf a)] {\bf Logarithmieren\index{Logarithmieren} (Bestimmen von $c$) -- Diskretes Logarithmus Problem\index{Logarithmusproblem!diskret}:}
Wenn man von den drei Zahlen $a, b, c$, welche diese Gleichung erf"ullen, $a$ und
$b$ kennt, ist jede bekannte Methode, $c$ zu finden, ungef"ahr so aufwendig wie
das Durchprobieren aller $m$ denkbaren Werte f"ur $c$ -- bei einem typischen $m$ in
der Gr"o"senordnung von $10^{180}$ f"ur $600$-stellige Bin"arzahlen ein hoffnungsloses
Unterfangen. Genauer ist f"ur geeignet gro"se Zahlen $m$ der Aufwand nach heutigem
Wissensstand proportional zu ${\rm exp}\left( C*( \log m [\log \log m]^2)^{1/3}\right)$ mit einer
Konstanten $C > 1$.
\item[\bf b)] {\bf Wurzel-Berechnung (Bestimmen von $b$):}
"Ahnliches gilt, wenn $b$ die Unbekannte ist und die Zahlen $a$ und $c$ bekannt sind. \\
Wenn die Eulerfunktion \index{Eulersche Phi-Funktion} $J(m)$ bekannt ist, findet man
leicht\footnote{%
Siehe \hyperlink{Appendix_A}{Anhang A zu diesem Kapitel}: der gr"o"ste gemeinsame Teiler (ggT) von ganzen Zahlen.
} $d$ mit $c*d \equiv 1 {\rm ~(mod~} J(m))$ und erh"alt mit Satz \ref{thm-zth-pot}
$$
a^d \equiv (b^c)^d \equiv b^{c*d} \equiv b^{c*d~(mod~J(m))} \equiv b^1 \equiv b {\rm ~(mod~} m)
$$
die {\em $c$-te Wurzel} $b$ von $a$. \par
F"ur den Fall, dass $J(m)$ in der Praxis nicht bestimmt werden
kann\footnote{%
Nach dem ersten Hauptsatz der Zahlentheorie und Satz \ref{thm-zth-phinum} kann man $J(m)$ mit Hilfe
der Primfaktorzerlegung\index{Primfaktor!Zerlegung} von $m$ bestimmen.
}, ist die Berechnung der $c$-ten Wurzel schwierig. Hierauf beruhen die Sicherheitsannahmen f"ur das
RSA-Kryptosystem (siehe Kapitel \ref{rsabeweis} oder Kapitel
\ref{rsaverfahren}).
\end{itemize}
Dagegen ist der Aufwand f"ur die Umkehrung von Addition und Multiplikation
nur proportional zu $\log m$ beziehungsweise $(\log m)^2$.
Potenzieren (zu einer Zahl $x$ berechne $x^a$ mit festem $a$) und Exponentiation
(zu einer Zahl $x$ berechne $a^x$ mit festem $a$) sind also typische Einwegfunktionen\index{Einwegfunktion}
(siehe "Ubersicht "uber Einwegfunktionen im \hyperlink{OneWayFunktion1}{Skript} oder in diesem \hyperlink{OneWayFunktion2}{Artikel}).
% ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\subsection{Gruppen und modulare Arithmetik "uber $ \mathbb{Z}_n\; $ und $ \mathbb{Z}^*_n $}
\index{Gruppen}
In der Zahlentheorie und in der Kryptographie spielen mathematische
\glqq {\em Gruppen}'' eine entscheidende Rolle. Von Gruppen spricht man nur, wenn f"ur
eine definierte Menge und eine definierte Relation (eine Operation wie
Addition oder Multiplikation) die folgenden Eigenschaften erf"ullt sind:
\begin{itemize}
\item Abgeschlossenheit \index{Abgeschlossenheit}
\item Existenz des neutralen Elements
\item Existenz eines inversen Elements zu jedem Element und
\item G"ultigkeit des Assoziativgesetzes.
\end{itemize}
Die abgek"urzte mathematische Schreibweise lautet: $(G, +)$ oder $(G,*)$.
\begin{definition}\label{def-zth-zn}
$\mathbb{Z}_n$ :\index{Z@$\mathbb{Z}_n$}
$$\mathbb{Z}_n \text{ umfasst alle ganzen Zahlen von } 0 \text{ bis } n-1: \mathbb{Z}_n = \{0, 1, 2,\cdots, n-2, n-1\}.$$
\end{definition}
$\mathbb{Z}_n$ ist eine h"aufig verwendete endliche Gruppe aus den nat"urlichen Zahlen. Sie
wird manchmal auch als Restemenge $R$ modulo $n$ bezeichnet.
Beispielsweise rechnen 32 Bit-Computer ("ubliche PCs) mit ganzen Zahlen
direkt nur in einer endlichen Menge, n"amlich in dem Wertebereich $0, 1, 2,
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -