diff options
| -rw-r--r-- | buch/chapters/30-endlichekoerper/rechnungen/euinv.maxima | 31 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/wurzeln.tex | 203 |
2 files changed, 232 insertions, 2 deletions
diff --git a/buch/chapters/30-endlichekoerper/rechnungen/euinv.maxima b/buch/chapters/30-endlichekoerper/rechnungen/euinv.maxima new file mode 100644 index 0000000..ce5b7f2 --- /dev/null +++ b/buch/chapters/30-endlichekoerper/rechnungen/euinv.maxima @@ -0,0 +1,31 @@ +m: X^3 +2*X^2 + 2*X + 3; +f: 2*X^2 + 2*X + 1; + +q0: 4*X+4; +r0: 4*X+6; +expand(q0*f+r0); + +q1: 4*X+5; +r1: 6; +expand(q1*r0+r1); + +q2: 3*X+1; +r2: 0; +expand(q2*r1+r2); + +Q0: matrix([ 0, 1 ], [ 1, (7*X+7)-q0 ]); +Q1: matrix([ 0, 1 ], [ 1, (7*X+7)-q1 ]); +Q2: matrix([ 0, 1 ], [ 1, (7*X+7)-q2 ]); + +Q: expand(Q1 . Q0); +s: Q[1,1]; +t: Q[1,2]; +expand(s*m+t*f); + +Q: expand(Q2 . Q); + +s: Q[1,1]; +t: Q[1,2]; + +expand(s*m+t*f); + diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index 2ea43e2..4925ad4 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -175,7 +175,7 @@ a_0+a_1\alpha+a_2\alpha^2+\dots+a_{n-1}\alpha^{n-1}\;|\; a_i\in\Bbbk\}. \} \] Die Addition von solchen Ausdrücken und die Multiplikation mit Skalaren -aus $\Bbbk$ machen $\Bbbk(\alpha)\simeq \Bbbk^n$ zu einem Vektorraum, +aus $\Bbbk$ machen $\Bbbk(\alpha)\cong \Bbbk^n$ zu einem Vektorraum, die Operationen können auf den Koeffizienten komponentenweise ausgeführt werden. @@ -479,14 +479,213 @@ $2m(X)$ subtrahieren:} \end{align*} das Element $b(\alpha)=6\alpha+5\alpha^2$ ist also das Inverse Element von $a(\alpha)=1+2\alpha+2\alpha^2$ in $\mathbb{F}_7(\alpha)$. +\label{buch:endlichekoerper:beispiel:inversemitmatrix} \end{beispiel} Die Matrixrealisation von $\Bbbk(\alpha)$ führt also auf eine effiziente Berechnungsmöglichkeit für das Inverse eines Elements von $\Bbbk(\alpha)$. +\subsubsection{Algebraische Konstruktion} +Die Matrixdarstellung von $\alpha$ ermöglicht eine rein algebraische +und für die Rechnung besser geeignete Konstruktion. +Für jedes Polynom $f\in\Bbbk[X]$ ist $f(M_\alpha)\in M_n(\Bbbk)$. +Dies definiert einen Homomorphismus +\[ +\varphi\colon \Bbbk[X] \to M_n(\Bbbk) : f \mapsto f(M_\alpha). +\] +Wir haben früher schon gesehen, dass das Bild dieses Homomorphismus +genau die Menge $\Bbbk(M_\alpha)$ ist. +Allerdings ist $\varphi$ nicht injektiv, das Polynom $m$ wird zum +Beispiel auf $\varphi(m) = m(M_\alpha) = 0$ abgebildet. + +Der Kern von $\varphi$ besteht aus allen Polynomen $p\in\Bbbk[X]$, +für die $p(M_\alpha)=0$ gilt. +Da aber alle Matrizen $E,M_\alpha,\dots,M_\alpha^{n-1}$ linear +unabhängig sind, muss ein solches Polynom den gleichen Grad haben +we $m$, und damit ein Vielfaches von $m$ sein. +Der Kern besteht daher genau aus den Vielfachen von $m(X)$, +$\ker\varphi = m(X)\Bbbk[X]$. + +Es ist nicht a priori klar, dass der Quotient $R/I$ für ein +Ideal $I\subset R$ ein Körper ist. +Hier spielt es eine Rolle, dass das von $m$ erzeugte Ideal +maximal ist im folgenden Sinne. + +\begin{definition} +Ein Ideal $I\subset R$ heisst {\em maximal}, wenn für jedes andere Ideal +$J$ mit $I\subset J\subset R$ entweder $I=J$ oder $J=R$ gilt. +\end{definition} + +\begin{beispiel} +Die Ideale $p\mathbb{Z}\subset \mathbb{Z}$ sind maximal genau dann, wenn +$p$ eine Primzahl ist. + +TODO: XXX Begründung +\end{beispiel} + +\begin{satz} +Der Ring $R/I$ ist genau dann ein Körper, wenn $I$ ein maximales Ideal ist. +\end{satz} + +\begin{proof}[Beweis] +\end{proof} + +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)$} +Die algebraische Konstruktion hat gezeigt, dass die arithmetischen +Operationen im Körper $\Bbbk(\alpha)$ genau die Operationen +in $\Bbbk[X]/m\Bbbk[X]$ sind. +Eine Zahl in $\Bbbk(\alpha)$ wird also durch ein Polynom vom +$n-1$ dargestellt. +Addieren und Subtrahieren erfolgen Koeffizientenweise in $\Bbbk$. +Bei der Multiplikation entsteht möglicherwise ein Polynom grösseren +Grades, mit dem Polynomdivisionsalgorithmus kann der Rest bei Division +durch $m$ ermittelt werden. -\subsubsection{Algebraische Konstruktion} +\begin{beispiel} +XXX: Reduktionsbeispiel +\end{beispiel} + +Die schwierigste Operation 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, +dass +\[ +af+bm=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$. + +\begin{beispiel} +% XXX verweise auf das frühere Beispiel +Wir berechnen 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$. + +Zunächst müssen wir den euklidischen Algorithmus für die beiden Polynome +$f$ und $m$ durchführen. +Der Quotient $m:f$ ist: +\[ +\arraycolsep=1.4pt +\begin{array}{rcrcrcrcrcrcrcrcr} + X^3&+&2X^2&+&2X&+&3&:&2X^2&+&2X&+&1&=&4X&+&4\rlap{$\mathstrut=q_0$}\\ +\llap{$-($}X^3&+& X^2&+&4X\rlap{$)$}& & & & & & & & & & & & \\ \cline{1-5} + & & X^2&+&5X&+&3& & & & & & & & & & \\ + &&\llap{$-(\phantom{2}$}X^2&+& X&+&4\rlap{$)$}& & & & & & & & & & \\ \cline{3-7} + & & & &4X&+&6\rlap{$\mathstrut=r_0$}& & & & & & & & & & +\end{array} +\] +Jetzt muss der Quotient $f:r_0$ berechnet werden: +\[ +\arraycolsep=1.4pt +\begin{array}{rcrcrcrcrcrcrcrcr} + 2X^2&+&2X&+&1&:&4X&+&6&=&4X&+&5\rlap{$\mathstrut=q_1$}\\ +\llap{$-($}2X^2&+&3X\rlap{$)$}& & & & & & & & \\ \cline{1-3} + & &6X&+&1& & & & & & \\ + & &\llap{$-($}6X&+&2\rlap{$)$}& & & & & & \\ \cline{3-5} + & & & &6\rlap{$\mathstrut=r_1$}& & & & & & & & +\end{array} +\] +\[ +\arraycolsep=1.4pt +\begin{array}{rcrcrcrcr} +4X&+&6&:&6&=&3X&+&1\rlap{$\mathstrut=q_2$} \\ +\llap{$-($}4X\rlap{$)$}& & & & & & & & \\ \cline{1-1} + 0&+&6& & & & & & \\ + & &\llap{$-($}6\rlap{$)$}& & & & & &\\ \cline{3-3} + & &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. +Durch Ausmultiplizieren der Matrizen können wir jetzt auch die +Faktoren $a$ und $b$ finden. +\begin{align*} +Q&= Q(q_2)Q(q_1)Q(q_0) += +\begin{pmatrix}0&1\\1&-q_2\end{pmatrix} +\begin{pmatrix}0&1\\1&-q_1\end{pmatrix} +\begin{pmatrix}0&1\\1&-q_0\end{pmatrix} +\\ +&= +\begin{pmatrix} +0&1\\ +1&4X+6 +\end{pmatrix} +\begin{pmatrix} +0&1\\ +1&3X+2 +\end{pmatrix} +\begin{pmatrix} +0&1\\ +1&3X+3 +\end{pmatrix} +\\ +&= +\begin{pmatrix} +0&1\\ +1&4X+6 +\end{pmatrix} +\begin{pmatrix} + 1&3X+3\\ +3X+2&2X^2 + X +\end{pmatrix} +\\ +&= +\begin{pmatrix} +3X+2 &2X^2+X\\ +1+(4X+6)(3X+2) &3X+3 + (4X+6)(2X^2+X) +\end{pmatrix} +\\ +&= +\begin{pmatrix} + 3X+2 & 2X^2 +X\\ +5X^2+5X+6 & X^3+2X^2+2X+6 +\end{pmatrix} +\end{align*} +Daraus liest man +\[ +a += +3X+2 +\qquad\text{und}\qquad +b += +2X^2+X +\] +ab. +Wir überprüfen, ob die Koeffizienten der ersten Zeile tatsächlich $m$ und $f$ +zu $1$ kombinieren. +Es ist +\begin{align*} +(3X+2)\cdot m + (2X^2+X)\cdot f +&= +(3X+2) +(X^3+3X^2+X+2) ++ +(2X^2+X) +(2X^2+2X+1) +\\ +&= +6 +\end{align*} +Die multiplikative Inverse ist daher +$-(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$. + +TODO: XXX Arithmetik in $\mathbb{F}_2$ erklären \subsection{Zerfällungskörper} |