aboutsummaryrefslogtreecommitdiffstats
path: root/buch
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-02-09 18:21:20 +0100
committerAndreas Müller <andreas.mueller@ost.ch>2021-02-09 18:21:20 +0100
commit8db04cfeeb7e3f7cb3541287196ebbab46fd8373 (patch)
tree122179a015d659b5610ddfd9b6bc2b928530098e /buch
parentEinleitung Wurzeln (diff)
downloadSeminarMatrizen-8db04cfeeb7e3f7cb3541287196ebbab46fd8373.tar.gz
SeminarMatrizen-8db04cfeeb7e3f7cb3541287196ebbab46fd8373.zip
Reduktion
Diffstat (limited to '')
-rw-r--r--buch/chapters/30-endlichekoerper/wurzeln.tex207
1 files changed, 183 insertions, 24 deletions
diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex
index 2f80fb0..2cbd004 100644
--- a/buch/chapters/30-endlichekoerper/wurzeln.tex
+++ b/buch/chapters/30-endlichekoerper/wurzeln.tex
@@ -416,7 +416,7 @@ Wir betrachten das Polynom
\[
m(X) = X^3 + 2X^2 + 2X + 3 \in \mathbb{F}_{7}[X],
\]
-es irreduzibel.
+es ist irreduzibel.
Sei $\alpha$ eine Nullstelle von $m$, wir suchen das inverse Element zu
\[
a(\alpha)=1+2\alpha+2\alpha^2\in\mathbb{F}_{7}(\alpha).
@@ -430,7 +430,52 @@ A=\begin{pmatrix}
\end{pmatrix}.
\]
Die Inverse kann man bestimmen, indem man den
-Gauss-Algorithmus in $\mathbb{F}_{17}$ durchführt.
+Gauss-Algorithmus in $\mathbb{F}_{7}$ durchführt.
+Die Arithmetik in $\mathbb{F}_{7}$ ist etwas ungewohnt, insbesondere
+die Pivot-Division ist etwas mühsam, daher sind in
+Abbildung~\label{buch:endlichekoerper:fig:additionmultiplikation}
+die Additions- und Multiplikationstabellen zusammengestellt.
+\begin{figure}
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
++&0&1&2&3&4&5&6\\
+\hline
+0&0&1&2&3&4&5&6\\
+1&1&2&3&4&5&6&0\\
+2&2&3&4&5&6&0&1\\
+3&3&4&5&6&0&1&2\\
+4&4&5&6&0&1&2&3\\
+5&5&6&0&1&2&3&4\\
+6&6&0&1&2&3&4&5\\
+\hline
+\end{tabular}
+\qquad
+\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+\cdot
+ &0&1&2&3&4&5&6\\
+\hline
+0&0&0&0&0&0&0&0\\
+1&0&1&2&3&4&5&6\\
+2&0&2&4&6&1&3&5\\
+3&0&3&6&2&5&1&4\\
+4&0&4&1&5&2&6&3\\
+5&0&5&3&1&6&4&2\\
+6&0&6&5&4&3&2&1\\
+\hline
+\end{tabular}
+\end{center}
+\caption{Additions- und Multiplikationstabelle für das Rechnen im
+Galois-Körper $\mathbb{F}_7$.
+Die multiplikative Inverse eines Elements in $a\in\mathbb{F}_7^*$
+findet man, indem man in der Multiplikationstabelle in der Zeile
+$a$ die Spalte mit der $1$ sucht, diese Spalte ist mit der multiplikativen
+Inversen von $a$ angeschrieben.
+\label{buch:endlichekoerper:fig:additionmultiplikation}}
+\end{figure}
+Mit dieser Rechenhilfe kann jetzt der Gaussalgorithmus leicht durchgeführt
+werden:
\begin{align*}
\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
@@ -576,7 +621,7 @@ Der Ring $R/I$ ist genau dann ein Körper, wenn $I$ ein maximales Ideal ist.
Ein irreduzibles Polynom $m\in\Bbbk[X]$ erzeugt ein maximales Ideal,
somit ist $\Bbbk[X]/m\Bbbk[X]\cong \Bbbk(M_\alpha) \cong \Bbbk(\alpha)$.
-\subsubsection{Rechnen in $\Bbbk(\alpha)$}
+\subsubsection{Reduktion modulo $m$}
Die algebraische Konstruktion hat gezeigt, dass die arithmetischen
Operationen im Körper $\Bbbk(\alpha)$ genau die Operationen
in $\Bbbk[X]/m\Bbbk[X]$ sind.
@@ -588,29 +633,132 @@ Grades, mit dem Polynomdivisionsalgorithmus kann der Rest bei Division
durch $m$ ermittelt werden.
\begin{beispiel}
-XXX: Reduktionsbeispiel
+Das Polyonom $f=X^5+X^4+X^3+X^2+X^1+1\in\mathbb{F}_7[X]$ soll modulo
+$m(X)=X^3+2X^2+2X^2+3$ reduziert werden.
+Wir führen die Polynomdivision in $\mathbb{F}_7[X]$ durch, die
+Multiplikationstabelle von $\mathbb{F}_7$ in
+Abbildung~\ref{buch:endlichekoerper:fig:additionmultiplikation}
+ist dabei wieder hilfreich.
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcrcrcrcrcrcrcrcr}
+X^5&+& X^4&+& X^3&+& X^2&+& X&+&1&:&X^3&+&2X^2&+&2X&+&3&=&X^2&+&6X&+&1\rlap{$\mathstrut=q$}\\
+\llap{$-($}X^5&+&2X^4&+&2X^3&+&3X^2\rlap{$)$}& & & & & & & & & & & & & & & & & & \\
+\cline{1-7}
+ & &6X^4&+&6X^3&+&5X^2&+& X& & & & & & & & & & & & & & & & \\
+ & &\llap{$-($}6X^4&+&5X^3&+&5X^2&+&4X\rlap{$)$}& & & & & & & & & & & & & & & & \\
+\cline{3-9}
+ & & & & X^3& & &+&4X&+&1& & & & & & & & & & & & & & \\
+ & & & &\llap{$-($}X^3&+&2X^2&+&2X&+&3\rlap{$)$}& & & & & & & & & & & & & & \\
+\cline{5-11}
+ & & & & & &5X^2&+&2X&+&5\rlap{$\mathstrut=r$}& & & & & & & & & & & & & & \\
+\end{array}
+\]
+Die Kontrolle
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcrcr}
+\llap{$($}X^2&+& 6X&+& 1\rlap{$)$}&\cdot&\llap{$($} X^3&+&2X^2&+&2X&+&3\rlap{$)$}\\
+\cline{1-13}
+ & & & & & & X^3&+&2X^2&+&2X&+&3\\
+ & & & &6X^4& + &5X^3&+&5X^2&+&4X& & \\
+ & & X^5&+&2X^4& + &2X^3&+&3X^2& & & & \\
+\cline{3-13}
+ & & X^5&+& X^4& + & X^3&+&3X^2&+&6X&+&3\rlap{$\phantom{)}=q\cdot m$}\\
+ & & & & & & & &\llap{$+($}5X^2&+&2X&+&5\rlap{$)=r$}\\
+\cline{3-13}
+ & & X^5&+& X^4& + & X^3&+& X^2&+& X&+&1\\
+\cline{3-13}
+\end{array}
+\]
+zeigt $f=qm+r$ und damit die Korrektheit der Rechnung.
+\end{beispiel}
+
+Die Identität $m(\alpha)=0$ kann aber auch wie folgt interpretiert werden.
+Sei der Grad von $f$ mindestens so gross wie der von $m$, also
+$l=\deg f\ge \deg m=n$.
+Indem man mit $\alpha^{l-n}$ multipliziert, erhält man die Relation
+\[
+\alpha^l + m_{n-1}\alpha^{l-1} + m_{n-2}\alpha^{l-2}+\dots +a_1\alpha^{l-n+1} + a_0\alpha^{-l-n} = 0.
+\]
+
+Ist $f_l$ der führende Koeffizient des Polynoms $f$, dann ist
+$f-f_0mX^{n-l}$ ein Polynom vom Grad $l-1$, welches modulo $m$
+mit $f$ übereinstimmt.
+Indem man dies wiederholt, kann man also die Reduktion finden, ohne
+den Polynomdivisionsalgorithmus durchzuführen.
+Man erhält auf diese Weise zwar den Quotienten $q$ nicht, aber den
+Rest $r$ kann man trotzdem bekommen.
+
+\begin{beispiel}
+Wir wenden den eben beschriebenen Algorithmus wieder auf das
+Polynom $f=X^5+X^4+X^3+X^2+X+1$ an und erhalten:
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcr}
+X^5&+& X^4&+& X^3&+& X^2&+& X&+&1\\
+\llap{$-($}X^5&+&2X^4&+&2X^3&+&3X^2\rlap{$\mathstrut =X^2m)$}& & & & \\
+\cline{1-11}
+ & &6X^4&+&6X^3&+&5X^2&+& X&+&1\\
+ & &\llap{$-($}6X^4&+&5X^3&+&5X^2&+&4X\rlap{$\mathstrut =6Xm)$}& & \\
+\cline{3-11}
+ & & & & X^3& & &+&4X&+&1\\
+ & & & & \llap{$-($}X^3&+&2X^2&+&2X&+&3\rlap{$\mathstrut =m)$}\\
+\cline{5-11}
+ & & & & & &5X^2&+&2X&+&5\rlap{$\mathstrut =r$}\\
+\end{array}
+\]
+Dies ist derselbe Rest wie wir mit dem Divisionsalgorithmus
+gefunden haben.
\end{beispiel}
-Die schwierigste Operation ist die Division.
+Diese Form des Reduktionsalgorithmus ist besonders leicht durchzuführen
+in einem Körper $\mathbb{F}_2$, da dort die Addition und die Subtraktion
+der Koeffizienten dasselbe ist.
+Die Multiplikation mit $X$ ist nichts anders als ein Shift der
+Koeffizienten.
+
+\subsubsection{Multiplikative Inverse}
+Die schwierigste Operation in $\Bbbk(\alpha)$ ist die Division.
Wie bei der Berechnung der Inversion in einem Galois-Körper $\mathbb{F}_p$
kann dafür der euklidische Algorithmus verwendet werden.
Sei also $f\in\Bbbk[X]$ ein Polynom vom Grad $\deg f <\deg m$, es soll
das multiplikative Inverse gefunden werden.
Da $m$ ein irreduzibles Polynom ist, müssen $f$ und $m$ teilerfremd sein.
-Der euklidische Algorithmus liefert zwei Polynome $a,b\in\Bbbk[X]$ derart,
+Der euklidische Algorithmus liefert zwei Polynome $s,t\in\Bbbk[X]$ derart,
dass
\[
-af+bm=1.
+sf+tm=1.
\]
Reduzieren wir modulo $m$, wird daraus $af=1$ in $\Bbbk[X]/m\Bbbk[X]$.
Das Polynom $a$, reduziert module $m$, ist also die multiplikative
Inverse von $f$.
+Bei der praktischen Durchführung des euklidischen Algorithmus ist der
+letzte Rest $r_{n-1}$ oft nicht $1$ sondern ein anderes Element von
+$\mathbb{F}_p^*$.
+Die Linearkombination von $f$ und $m$ mit den berechneten Faktoren
+$s$ und $t$ ist daher auch nicht $1$, sondern
+\[
+sf+tm=r_{n-1}.
+\]
+Da aber alle Elemente in $\mathbb{F}_p^*$ invertierbar sind, kann man
+durch $r_{n-1}$ dividieren, was
+\[
+r_{n-1}^{-1}sf+r_{n-1}^{-1}tm=1
+\]
+ergibt.
+Also ist $r_{n-1}^{-1}s$ die gesuchte Inverse in $\mathbb{F}_p(\alpha)$,
+dies passiert auch im folgenden Beispiel.
+
\begin{beispiel}
-% XXX verweise auf das frühere Beispiel
-Wir berechnen die multiplikative Inverse von
+Auf
+Seite~\pageref{buch:endlichekoerper:beispiel:inversemitmatrix}
+haben wir die multiplikative Inverse von
$f=2X^2+2X+1\in\mathbb{F}_7[X]/m\mathbb{F}_7[X]$
-mit $m = X^3 + 2X^2 + 2X + 3$.
+mit $m = X^3 + 2X^2 + 2X + 3$
+mit Hilfe von Matrizen berechnet, hier soll sie jetzt nochmals
+mit dem euklidischen Algorithmus berechnet werden.
Zunächst müssen wir den euklidischen Algorithmus für die beiden Polynome
$f$ und $m$ durchführen.
@@ -646,8 +794,9 @@ Jetzt muss der Quotient $f:r_0$ berechnet werden:
& &0\rlap{$\mathstrut=r_2$}& & & & & &
\end{array}
\]
-Die nächste Division ergibt natürlich den Rest $0$ und $6=-1$ ist der
-erwartete grösste gemeinsame Teiler.
+Die nächste Division ergibt natürlich den Rest $0$ und
+der letzte nicht verschwindende Rest ist $r_{1}=6$.
+
Durch Ausmultiplizieren der Matrizen können wir jetzt auch die
Faktoren $a$ und $b$ finden.
\begin{align*}
@@ -695,17 +844,17 @@ Q&= Q(q_2)Q(q_1)Q(q_0)
\end{align*}
Daraus liest man
\[
-a
+s
=
-3X+2
+2X^2+X
\qquad\text{und}\qquad
-b
+t
=
-2X^2+X
+3X+2
\]
ab.
Wir überprüfen, ob die Koeffizienten der ersten Zeile tatsächlich $m$ und $f$
-zu $1$ kombinieren.
+zu $r_1=6$ kombinieren.
Es ist
\begin{align*}
(3X+2)\cdot m + (2X^2+X)\cdot f
@@ -715,22 +864,32 @@ Es ist
+
(2X^2+X)
(2X^2+2X+1)
-\\
-&=
-6
+=
+6=r_1
\end{align*}
Die multiplikative Inverse ist daher
-$-(2X^2 + X) = 5X^2+6X$,
+$
+r_1^{-1}(2X^2 + X)
+=
+6^{-1}
+(2X^2 + X)
+=
+6
+(2X^2 + X)
+=
+5X^2+6X$,
was mit dem Beispiel von
Seite~\pageref{buch:endlichekoerper:beispiel:inversemitmatrix}
übereinstimmt.
\end{beispiel}
Besonders einfach ist die Rechung für $\Bbbk=\mathbb{F}_2$.
+Dieser Spezialfall ist für die praktische Anwendung in der Kryptographie
+von besonderer Bedeutung, daher wird er im
+In Kapitel~\ref{buch:chapter:kryptographie} genauer untersucht.
-TODO: XXX Arithmetik in $\mathbb{F}_2$ erklären
-
-\subsection{Zerfällungskörper}
+\subsection{Zerfällungskörper
+\label{buch:subsection:zerfaellungskoerper}}