diff options
| -rw-r--r-- | buch/chapters/30-endlichekoerper/wurzeln.tex | 207 |
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}} |