From 3cc801ff90729bc7c168cf74df2763e52f3fdc43 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 9 Jan 2021 17:07:25 +0100 Subject: add problem to chapter 3 --- .../30-endlichekoerper/uebungsaufgaben/3001.tex | 102 +++++++++++++++++++++ 1 file changed, 102 insertions(+) create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben') diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex new file mode 100644 index 0000000..7e40dfe --- /dev/null +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex @@ -0,0 +1,102 @@ +Im Rahmen der Aufgabe, die Zehntausernderstelle der Zahl $5^{5^{5^{5^5}}}$ +zu berechnen muss Michael Penn im Video +\url{https://youtu.be/Xg24FinMiws} bei 12:52 zwei Zahlen $x$ und $y$ finden, +so dass, +\[ +5^5x ++ +2^5y += +1 +\] +ist. +Verwenden Sie die Matrixform des euklidischen Algorithmus. + +\begin{loesung} +Zunächst berechnen wir die beiden Potenzen +\[ +5^5 = 3125 +\qquad\text{und}\qquad +2^5 = 32. +\] +Damit können wir jetzt den Algorithmus durchführen. +Die Quotienten und Reste sind +\begin{align*} +a_0&=q_0\cdot b_0 + r_0& +3125 &= 97 \cdot 32 + 21& q_0&=97 & r_0&= 21\\ +a_1&=q_1\cdot b_1 + r_1& +32 &= 1\cdot 21 + 10 & q_1&= 1 & r_1&= 11\\ +a_2&=q_2\cdot b_2 + r_2& +21 &= 1\cdot 11 + 10 & q_2&= 1 & r_2&= 10\\ +a_3&=q_3\cdot b_3 + r_3& +11 &= 1\cdot 10 + 1 & q_3&= 1 & r_3&= 1\\ +a_4&=q_4\cdot b_4 + r_4& +10 &= 10\cdot 1 + 0 & q_4&=10 & r_4&= 0 +\end{align*} +Daraus kann man jetzt auch die Matrizen $Q(q_k)$ bestimmen und +ausmultiplizieren: +\begin{align*} +Q +&= +\begin{pmatrix} +0&1\\1&-10 +\end{pmatrix} +\underbrace{ +\begin{pmatrix} +0&1\\1&-1 +\end{pmatrix} +\begin{pmatrix} +0&1\\1&-1 +\end{pmatrix} +}_{} +\underbrace{ +\begin{pmatrix} +0&1\\1&-1 +\end{pmatrix} +\begin{pmatrix} +0&1\\1&-97 +\end{pmatrix} +}_{} +\\ +&= +\begin{pmatrix} +0&1\\1&-10 +\end{pmatrix} +\underbrace{ +\begin{pmatrix} +0&-1\\-1&2 +\end{pmatrix} +\begin{pmatrix} +1&-97\\-1&98 +\end{pmatrix} +}_{} +\\ +&= +\underbrace{ +\begin{pmatrix} +0&1\\1&-10 +\end{pmatrix} +\begin{pmatrix} +2&-195\\-3&293 +\end{pmatrix} +}_{} +\\ +&= +\begin{pmatrix} +-3&293\\32&-3125 +\end{pmatrix}. +\end{align*} +Daras kann man jetzt ablesen, dass +\[ +-3\cdot 3125 ++ +293\cdot 32 += +-9375 ++ +9376 += +1. +\] +Die gesuchten Zahlen sind also $x=-3$ und $y=293$. +\end{loesung} -- cgit v1.2.1 From b1bb5a5e1d7d43a27e601a5df5cb212512458fc0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 24 Jan 2021 13:05:42 +0100 Subject: galois fields, exercise 3002 --- buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex | 2 +- buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex | 9 +++++++++ 2 files changed, 10 insertions(+), 1 deletion(-) create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben') diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex index 7e40dfe..9d47f85 100644 --- a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex @@ -1,4 +1,4 @@ -Im Rahmen der Aufgabe, die Zehntausernderstelle der Zahl $5^{5^{5^{5^5}}}$ +Im Rahmen der Aufgabe, die Zehntauserderstelle der Zahl $5^{5^{5^{5^5}}}$ zu berechnen muss Michael Penn im Video \url{https://youtu.be/Xg24FinMiws} bei 12:52 zwei Zahlen $x$ und $y$ finden, so dass, diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex new file mode 100644 index 0000000..83bfd0e --- /dev/null +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex @@ -0,0 +1,9 @@ +Berechnen Sie $666^{666}$ in $\mathbb{F}_{13}$. + +\begin{loesung} +Zunächst ist die Basis der Potenz $666=3$ in $\mathbb{F}_{13}$, es +muss also nur $3^{666}$ berechnet werden. +Nach dem kleinen Satz von Fermat ist $3^{12}=1$ in $\mathbb{F}_{13}$. +Wegen $666 = 12*50+6$ folgt +$ 3^{666} = 3^6=729=1$ in $\mathbb{F}_{13}$. +\end{loesung} -- cgit v1.2.1 From f63a0b8fc29db1e1c5891df0842a8126d75a51b4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 24 Jan 2021 20:40:53 +0100 Subject: =?UTF-8?q?Zus=C3=A4tzliches=20zu=20endlichen=20K=C3=B6rpern?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben') diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex index 83bfd0e..63200a7 100644 --- a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex @@ -4,6 +4,6 @@ Berechnen Sie $666^{666}$ in $\mathbb{F}_{13}$. Zunächst ist die Basis der Potenz $666=3$ in $\mathbb{F}_{13}$, es muss also nur $3^{666}$ berechnet werden. Nach dem kleinen Satz von Fermat ist $3^{12}=1$ in $\mathbb{F}_{13}$. -Wegen $666 = 12*50+6$ folgt +Wegen $666 = 12\cdot 50+6$ folgt $ 3^{666} = 3^6=729=1$ in $\mathbb{F}_{13}$. \end{loesung} -- cgit v1.2.1 From b3cce2ced8645128bbb2a3206f3bd1714ec2e416 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 4 Feb 2021 18:38:23 +0100 Subject: typo --- buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben') diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex index 9d47f85..4f4d56d 100644 --- a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex @@ -1,4 +1,4 @@ -Im Rahmen der Aufgabe, die Zehntauserderstelle der Zahl $5^{5^{5^{5^5}}}$ +Im Rahmen der Aufgabe, die Zehntausenderstelle der Zahl $5^{5^{5^{5^5}}}$ zu berechnen muss Michael Penn im Video \url{https://youtu.be/Xg24FinMiws} bei 12:52 zwei Zahlen $x$ und $y$ finden, so dass, -- cgit v1.2.1 From e89e7949b93d684c387db5062b2743c0207205ca Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 7 Mar 2021 18:40:42 +0100 Subject: two new problems --- .../30-endlichekoerper/uebungsaufgaben/3003.tex | 72 +++++++ .../30-endlichekoerper/uebungsaufgaben/3004.tex | 231 +++++++++++++++++++++ .../uebungsaufgaben/3004/matrix.m | 21 ++ 3 files changed, 324 insertions(+) create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben') diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex new file mode 100644 index 0000000..83ba7f2 --- /dev/null +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex @@ -0,0 +1,72 @@ +Die Zahl $p=47$ ist eine Primzahl, der Ring +$\mathbb{Z}/p\mathbb{Z}=\mathcal{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}$. + +\begin{loesung} +Der euklidische Algorithmus muss auf die Zahlen $p=47$ und $b=11$ angewendet +werden, es ergeben sich die Quotienten und Reste der folgenden Tabelle: +\begin{center} +\begin{tabular}{|>{$}c<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} +\hline +k&a_k&b_k&q_k&r_k\\ +\hline +0& 47& 11& 4& 3\\ +1& 11& 3& 3& 2\\ +2& 3& 2& 1& 1\\ +3& 2& 1& 2& 0\\ +\hline +\end{tabular} +\end{center} +Wie erwartet ist der grösste gemeinsame Teiler +$\operatorname{ggT}(47,11)=r_2=1$. +Um die Zahlen $s,t$ zu finden, für die $sp+tb=1$ gilt, können wir die +Matrixform verwenden, wir berechnen dazu +\begin{align*} +Q += +Q(2)Q(1)Q(3)Q(4) +&= +\begin{pmatrix} 0&1\\1&-2 \end{pmatrix} +\begin{pmatrix} 0&1\\1&-1 \end{pmatrix} +\begin{pmatrix} 0&1\\1&-3 \end{pmatrix} +\begin{pmatrix} 0&1\\1&-4 \end{pmatrix} +\\ +&= +\begin{pmatrix} 0&1\\1&-2 \end{pmatrix} +\begin{pmatrix} 0&1\\1&-1 \end{pmatrix} +\begin{pmatrix} 1&-4\\-3&13\end{pmatrix} +\\ +&= +\begin{pmatrix} 0&1\\1&-2 \end{pmatrix} +\begin{pmatrix} -3&13\\4&-17 \end{pmatrix} +\\ +&= +\begin{pmatrix} 4&-17\\ -11&47 \end{pmatrix}. +\end{align*} +Daraus kann man ablesen, dass $s=4$ und $t=-17$, tatsächlich ist +$4\cdot 47-47\cdot 11=188-187=1$. +Wir schliessen daraus, dass $-17=30\in\mathbb{F}_{47}$ die multiplikative +Inverse von $b=11$ ist. +Die Rechnung $11\cdot 30 = 330 = 7\cdot 47 + 1$ zeigt, dass dies +der Fall ist. + +Alternativ zur Matrixdarstellung kann man die Koeffizienten $s$ und $t$ +auch mit Hilfe der erweiterten Tabelle finden: +\begin{center} +\begin{tabular}{|>{$}c<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} +\hline +k&a_k&b_k&q_k&r_k&c_k&d_k\\ +\hline + & & & & & 1& 0\\ +0& 47& 11& 4& 3& 0& 1\\ +1& 11& 3& 3& 2& 1& -4\\ +2& 3& 2& 1& 1& -3& 13\\ +3& 2& 1& 2& 0& {\color{red}4}&{\color{red}-17}\\ +4& 1& 0& & &-11& 47\\ +\hline +\end{tabular} +\end{center} +Die gesuchten Zahlen $s$ und $t$ sind rot hervorgehoben. +\end{loesung} diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex new file mode 100644 index 0000000..66ac560 --- /dev/null +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex @@ -0,0 +1,231 @@ +Der Körper $\mathbb{F}_2$ ist besonders einfach, da er nur zwei Elemente +$0$ und $1$ enthält. +Die Additions- und Multiplikationstabellen sind +\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,2.5}{ + \draw \punkt{\x}{-0.5} -- \punkt{\x}{2.5}; + } + \foreach \y in {-0.5,0.5,2.5}{ + \draw \punkt{-0.5}{\y} -- \punkt{2.5}{\y}; + } + \node at \punkt{1}{0} {$0$}; + \node at \punkt{2}{0} {$1$}; + \node at \punkt{0}{1} {$0$}; + \node at \punkt{0}{2} {$0$}; +} +\begin{scope}[xshift=-3cm] + \tabelle + \node at (0,0) {$+$}; + \node at \punkt{1}{1} {$0$}; + \node at \punkt{2}{1} {$1$}; + \node at \punkt{1}{2} {$1$}; + \node at \punkt{2}{2} {$0$}; +\end{scope} +\begin{scope}[xshift=3cm] + \tabelle + \node at (0,0) {$\cdot$}; + \node at \punkt{1}{1} {$0$}; + \node at \punkt{2}{1} {$0$}; + \node at \punkt{1}{2} {$0$}; + \node at \punkt{2}{2} {$1$}; +\end{scope} +\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} +\item +Die Gauss-Tableaux sind +\begin{align*} +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1\\ + 0 & 1 & 1 & 1 & 0\\ + 1 & 1 & 1 & 1 & 0\\ + 0 & 1 & 1 & 0 & 1\\ +\hline +\end{tabular} +&\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1\\ + 0 & 1 & 1 & 1 & 0\\ + 0 & 0 & 1 & 1 & 1\\ + 0 & 1 & 1 & 0 & 1\\ +\hline +\end{tabular} +%\\ +%& +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1\\ + 0 & 1 & 1 & 1 & 0\\ + 0 & 0 & 1 & 1 & 1\\ + 0 & 0 & 0 & 1 & 1\\ +\hline +\end{tabular} +\\ +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1\\ + 0 & 1 & 1 & 0 & 1\\ + 0 & 0 & 1 & 0 & 0\\ + 0 & 0 & 0 & 1 & 1\\ +\hline +\end{tabular} +%\\ +& +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1\\ + 0 & 1 & 0 & 0 & 1\\ + 0 & 0 & 1 & 0 & 0\\ + 0 & 0 & 0 & 1 & 1\\ +\hline +\end{tabular} +%\\ +%& +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 0 & 0 & 0 & 0\\ + 0 & 1 & 0 & 0 & 1\\ + 0 & 0 & 1 & 0 & 0\\ + 0 & 0 & 0 & 1 & 1\\ +\hline +\end{tabular} +\end{align*} +In der ersten Zeile stehen die Schritt der Vorwärtsreduktion, in der +zweiten die Schritte des Rückwärtseinsetzens. +Als Lösung liest man ab +\[ +x=\begin{pmatrix}0\\1\\0\\1 \end{pmatrix}, +\] +die Korrektheit kann man leicht durch Einsetzen überprüfen. +\item +Wir wenden erneut den Gauss-Algorithmus an: +\begin{align*} +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ + 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ + 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ + 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ +\hline +\end{tabular} +&\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ + 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ + 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ +\hline +\end{tabular} +\\ +&\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ + 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ + 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ +\hline +\end{tabular} +\\ +&\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ + 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ + 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ + 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ +\hline +\end{tabular} +\\ +&\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline + 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ + 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ + 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ + 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ +\hline +\end{tabular} +\\ +&\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline + 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ + 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ + 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ + 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ +\hline +\end{tabular} +\end{align*} +Daraus liest man die Inverse $A^{-1}$ der Koeffizientenmatrix $A$ ab als +\[ +A^{-1} += +\begin{pmatrix} + 0 & 1 & 1 & 0 \\ + 1 & 1 & 1 & 0 \\ + 1 & 1 & 1 & 1 \\ + 0 & 1 & 0 & 1 +\end{pmatrix} +\] +\item Wir prüfen das Resultat durch Ausmultiplizieren: +\[ +AA^{-1} += +\begin{pmatrix} + 1 & 1 & 0 & 0 \\ + 0 & 1 & 1 & 1 \\ + 1 & 1 & 1 & 1 \\ + 0 & 1 & 1 & 0 +\end{pmatrix} +\begin{pmatrix} + 0 & 1 & 1 & 0 \\ + 1 & 1 & 1 & 0 \\ + 1 & 1 & 1 & 1 \\ + 0 & 1 & 0 & 1 +\end{pmatrix} += +\begin{pmatrix} + 1 & 0 & 0 & 0 \\ + 0 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 0 \\ + 0 & 0 & 0 & 1 +\end{pmatrix} +\] +Dabei kann man verwenden, dass der Eintrag in Zeile $i$ und Spalte $k$ des +Produktes die Anzahl der Positionen ist, wo in der Zeile $i$ von $A$ +und in der Spalte $j$ von $A^{-1}$ eine $1$ steht. +\end{teilaufgaben} +\end{loesung} diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m new file mode 100644 index 0000000..ed85185 --- /dev/null +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m @@ -0,0 +1,21 @@ +# +# matrix.m +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# + +n = 4 +N = 20; + +d = 0; +while d == 0 + A = round(N * rand(n,n)); + B = mod(A, 2); + d = det(B); + d = mod(d, 2); + d = d * B(1,1); +end +A +det(A) +B +det(B) -- cgit v1.2.1 From 1efe0e34e39901b06309d1bdcfb4750c37425aba Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 7 Mar 2021 20:15:34 +0100 Subject: =?UTF-8?q?neue=20=C3=9Cbungsaufgaben?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- .../30-endlichekoerper/uebungsaufgaben/3003.tex | 4 +- .../30-endlichekoerper/uebungsaufgaben/3004.tex | 49 ++--- .../30-endlichekoerper/uebungsaufgaben/3005.tex | 205 +++++++++++++++++++++ 3 files changed, 233 insertions(+), 25 deletions(-) create mode 100644 buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben') 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} -- cgit v1.2.1 From 9243858393d79e761f03b4454547310056d7fcea Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 7 Mar 2021 21:00:59 +0100 Subject: Gauss --- buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'buch/chapters/30-endlichekoerper/uebungsaufgaben') diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m index ed85185..42e9d9f 100644 --- a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m +++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m @@ -6,13 +6,14 @@ n = 4 N = 20; +p = 2; d = 0; while d == 0 A = round(N * rand(n,n)); - B = mod(A, 2); + B = mod(A, p); d = det(B); - d = mod(d, 2); + d = mod(d, p); d = d * B(1,1); end A -- cgit v1.2.1