diff options
Diffstat (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben')
3 files changed, 233 insertions, 25 deletions
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex index 83ba7f2..8a83256 100644 --- a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex @@ -1,8 +1,8 @@ Die Zahl $p=47$ ist eine Primzahl, der Ring -$\mathbb{Z}/p\mathbb{Z}=\mathcal{F}_{47}$ ist daher ein Körper. +$\mathbb{Z}/p\mathbb{Z}=\mathbb{F}_{47}$ ist daher ein Körper. Jeder von Null verschiedene Rest $b\in\mathbb{F}_p^*$ hat daher eine multiplikative Inverse. -Berechnen Sie die multiplikative Inverse von $b=11\in\mathcal{F}_{47}$. +Berechnen Sie die multiplikative Inverse von $b=11\in\mathbb{F}_{47}$. \begin{loesung} Der euklidische Algorithmus muss auf die Zahlen $p=47$ und $b=11$ angewendet diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex index 66ac560..046ac94 100644 --- a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex @@ -1,5 +1,28 @@ Der Körper $\mathbb{F}_2$ ist besonders einfach, da er nur zwei Elemente $0$ und $1$ enthält. +\begin{teilaufgaben} +\item +Bestimmen Sie die Additions- und Multiplikationstabelle für $\mathbb{F}_2$. +\item +Lösen Sie das lineare Gleichungssystem +\[ +\begin{linsys}{4} +x_1&+& x_2& & & & &=& 0\\ + & & x_2&+&x_3&+&x_4&=& 1\\ +x_1&+& x_2&+&x_3&+&x_4&=& 1\\ + & & x_2&+&x_3& & &=& 0\\ +\end{linsys} +\] +über dem Körper $\mathbb{F}_2$ mit dem Gauss-Algorithmus. +\item Bestimmen Sie die Inverse $A^{-1}\in \operatorname{GL}_2(\mathbb{F}_2)$ +der Koeffizientenmatrix $A$ des Gleichungssystems. +\item Kontrollieren Sie das Resultat durch Ausmultiplizieren des Produktes +$AA^{-1}$. +\end{teilaufgaben} + +\begin{loesung} +\begin{teilaufgaben} +\item Die Additions- und Multiplikationstabellen sind \begin{center} \begin{tikzpicture}[>=latex,thick] @@ -17,7 +40,7 @@ Die Additions- und Multiplikationstabellen sind \node at \punkt{0}{1} {$0$}; \node at \punkt{0}{2} {$0$}; } -\begin{scope}[xshift=-3cm] +\begin{scope}[xshift=-2cm] \tabelle \node at (0,0) {$+$}; \node at \punkt{1}{1} {$0$}; @@ -25,7 +48,7 @@ Die Additions- und Multiplikationstabellen sind \node at \punkt{1}{2} {$1$}; \node at \punkt{2}{2} {$0$}; \end{scope} -\begin{scope}[xshift=3cm] +\begin{scope}[xshift=2cm] \tabelle \node at (0,0) {$\cdot$}; \node at \punkt{1}{1} {$0$}; @@ -36,27 +59,7 @@ Die Additions- und Multiplikationstabellen sind \end{tikzpicture} \end{center} Betrachtet als Bitoperationen entspricht die Addition dem XOR, die -Multiplikation dem UND. -\begin{teilaufgaben} -\item -Lösen Sie das lineare Gleichungssystem -\[ -\begin{linsys}{4} -x_1&+& x_2& & & & &=& 0\\ - & & x_2&+&x_3&+&x_4&=& 1\\ -x_1&+& x_2&+&x_3&+&x_4&=& 1\\ - & & x_2&+&x_3& & &=& 0\\ -\end{linsys} -\] -über dem Körper $\mathcal{F}_2$ mit dem Gauss-Algorithmus. -\item Bestimmen Sie die Inverse $A^{-1}\in \operatorname{GL}_2(\mathbb{F}_2)$ -der Koeffizientenmatrix $A$ des Gleichungssystems. -\item Kontrollieren Sie das Resultat durch Ausmultiplizieren des Produktes -$AA^{-1}$. -\end{teilaufgaben} - -\begin{loesung} -\begin{teilaufgaben} +Multiplikation dem AND. \item Die Gauss-Tableaux sind \begin{align*} diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex new file mode 100644 index 0000000..28f4d2c --- /dev/null +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex @@ -0,0 +1,205 @@ +Das Polynom $m(X)=X^2+X+1$ ist als Polynom in $\mathbb{F}_3[X]$ irreduzibel. +Dies bedeutet, dass der Ring der Polynome $\mathbb{F}_3[X] / (m(X))$ +ein Körper ist, man bezeichnet ihn auch mit $\mathbb{F}_3(\alpha)$, +wobei man sich $\alpha$ als eine Nullstelle von $m(X)$ +oder als die Matrix +\[ +\alpha = \begin{pmatrix} 0&2\\1&2\end{pmatrix} +\] +vorstellen kann. +\begin{teilaufgaben} +\item +Stellen Sie die Additions- und Multiplikationstabellen für das Rechnen +in $\mathbb{F}_3$ auf. +\item +Berechnen Sie $\alpha^{-1}$ in $\mathbb{F}_3(\alpha)$ aus der +Bedingung $m(\alpha)=0$. +\item +Verwenden Sie den euklidischen Algorithmus, um $(1+\alpha)^{-1}$ +in $\mathbb{F}_3(\alpha)$ zu bestimmen. +\item +Berechnen Sie $\alpha^3$. +\end{teilaufgaben} + +\begin{loesung} +\begin{teilaufgaben} +\item +Die Additions- und Multiplikationstabelle von $\mathbb{F}_3$ ist +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\def\ds{0.5} +\def\punkt#1#2{({(#1)*\ds},{-(#2)*\ds})} +\def\tabelle{ +\foreach \x in {-0.5,0.5,3.5}{ + \draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5}; + \draw \punkt{-0.5}{\x} -- \punkt{3.5}{\x}; +} +\node at \punkt{0}{1} {$0$}; +\node at \punkt{0}{2} {$1$}; +\node at \punkt{0}{3} {$2$}; +\node at \punkt{1}{0} {$0$}; +\node at \punkt{2}{0} {$1$}; +\node at \punkt{3}{0} {$2$}; +} +\begin{scope}[xshift=-2cm] +\tabelle +\node at \punkt{0}{0} {$+$}; +\node at \punkt{1}{1} {$0$}; +\node at \punkt{1}{2} {$1$}; +\node at \punkt{1}{3} {$2$}; +\node at \punkt{2}{1} {$1$}; +\node at \punkt{2}{2} {$2$}; +\node at \punkt{2}{3} {$0$}; +\node at \punkt{3}{1} {$2$}; +\node at \punkt{3}{2} {$0$}; +\node at \punkt{3}{3} {$1$}; +\end{scope} +\begin{scope}[xshift=2cm] +\tabelle +\node at \punkt{0}{0} {$\cdot$}; +\node at \punkt{1}{1} {$0$}; +\node at \punkt{1}{2} {$0$}; +\node at \punkt{1}{3} {$0$}; +\node at \punkt{2}{1} {$0$}; +\node at \punkt{2}{2} {$1$}; +\node at \punkt{2}{3} {$2$}; +\node at \punkt{3}{1} {$0$}; +\node at \punkt{3}{2} {$2$}; +\node at \punkt{3}{3} {$1$}; +\end{scope} +\end{tikzpicture} +\end{center} +\item +Wegen $m(\alpha)=\alpha^2+\alpha+1=0$ folgt $\alpha+1+\alpha^{-1}=0$ +oder $\alpha^{-1} = -\alpha - 1 = 2+2\alpha$. +Als Matrix kann man +\[ +\alpha^{-1} += +2\alpha + 2 += +\begin{pmatrix} +0&4\\ +2&4 +\end{pmatrix} ++ +\begin{pmatrix} +2&0\\0&2 +\end{pmatrix} += +\begin{pmatrix} +2&4\\2&2 +\end{pmatrix} +\equiv +\begin{pmatrix}2&1\\2&0\end{pmatrix} +\mod 3 +\] +schreiben und durch Nachrechnen verifizieren dass, tatsächlich gilt +\[ +\alpha\alpha^{-1} += +\begin{pmatrix} +0&2\\ +1&2 +\end{pmatrix} +\begin{pmatrix} +2&1\\ +2&0 +\end{pmatrix} += +\begin{pmatrix} +4&0\\ +6&1 +\end{pmatrix} +\equiv +\begin{pmatrix} +1&0\\ +0&1 +\end{pmatrix} +\mod 3. +\] +\item +Für den euklidischen Algorithmus müssen wir wiederholt eine Polynomdivision +in $\mathbb{F}_3[X]$ durchführen. +Im ersten Schritt ist es +\[ +\arraycolsep=1.4pt +\begin{array}{rcrcrcrcrcr} + \llap{$($}X^2&+&X&+&1\rlap{$)$}&\;:&(X&+&1)&=&X = q_1\\ +\llap{$-($}X^2&+&X\rlap{$)$}& & & & & & & & \\ \cline{1-3} + & &0&+&1 &\rlap{$\mathstrut = r_1$}\phantom{)}& & & & & \\ +\end{array} +\] +Die nächste Division ist $(X+1) : 1$, die als Quotient $q_2=X+1$ und den +Rest $r_2=0$ hat. +Mit der Matrixform des euklidischen Algorithmus kann man jetzt auch die +Koeffizienten $s$ und $t$ bestimmen, die beide Polynome in $\mathbb{F}_3[X]$ +sind: +\begin{align*} +Q +&= +Q(q_2) +Q(q_1) += +\begin{pmatrix} +0&1\\1&-q_2 +\end{pmatrix} +\begin{pmatrix} +0&1\\1&-q_1 +\end{pmatrix} += +\begin{pmatrix} +0&1\\1&2X+2 +\end{pmatrix} +\begin{pmatrix} +0&1\\{\color{red}1}&{\color{red}2X} +\end{pmatrix} += +\begin{pmatrix} +{\color{red}1}&{\color{red}2X}\\ +2X&X^2+X+1 +\end{pmatrix}. +\end{align*} +Die gesuchten Polynome sind $s=1$ und $t=2X$ und man kann nachrechnen, +dass +\begin{align*} +s\cdot m(X) + t\cdot (X+1) +&= +X^2+X+1 + 2X\cdot (X+1) += +X^2+X+1 + 2X^2 + 2X +\\ +&= 3X^2+3X+1\equiv 1 \mod 3. +\end{align*} +Natürlich kann man $s$ und $t$ auch mit der erweiterten Tabelle +finden: +\begin{center} +\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|} +\hline +k& a_k&b_k& q_k&r_k& c_k& d_k\\ +\hline + & & & & & 1& 0\\ +0&X^2+X+1&X+1& X & 1& 0& 1\\ +1& X+1& 1& X+1& 0&{\color{red} 1}&{\color{red} 2X}\\ +2& 1& 0& & 0&2X+2& 2X^2+2X\\ +\hline +\end{tabular} +\end{center} +In allen Fällen ist also $(1+X)^{-1} = 2X$. +\item +Wegen $m(\alpha)=0$ ist $\alpha^2=-\alpha-1=2\alpha+2$ und damit +\begin{align*} +\alpha^3 +&= +\alpha\cdot \alpha^2 = \alpha (2\alpha +2) = +2\alpha^2 + 2\alpha += +2(\underbrace{\alpha^2 + \alpha + 1}_{\displaystyle=0} + 2) += +2\cdot 2 += +1. +\qedhere +\end{align*} +\end{teilaufgaben} +\end{loesung} |