diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/chapters/30-endlichekoerper/euklid.tex | 150 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/galois.tex | 6 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/rechnungen/rs.maxima | 29 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/wurzeln.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/arith.tex | 2 |
5 files changed, 184 insertions, 5 deletions
diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex index 8aa2f71..094a07a 100644 --- a/buch/chapters/30-endlichekoerper/euklid.tex +++ b/buch/chapters/30-endlichekoerper/euklid.tex @@ -519,6 +519,7 @@ Insbesondere ist der euklidische Algorithmus genauso wie die Matrixschreibweise auch für Polynome durchführbar. \begin{beispiel} +\label{buch:endlichekoerper:eqn:polynomggt} Wir berechnen als Beispiel den grössten gemeinsamen Teiler der Polynome \[ @@ -829,5 +830,154 @@ das kleinste gemeinsame Vielfache zweier Polynome zu berechnen. Dies wird zum Beispiel bei der Decodierung des Reed-Solomon-Codes in Kapitel~\ref{chapter:reedsolomon} verwendet. +\subsubsection{Polynome +\label{buch:endlichekoerper:eqn:polynomkgv}} +Im Beispiel auf Seite~\pageref{buch:endlichekoerper:eqn:polynomggt} +wird der grösste gemeinsame Teiler der Polynome +\[ +a += +X^4 - 2X^3 -7 X^2 + 8X + 12, +\qquad +b = X^4 + X^3 -7X^2 -X + 6 +\] +berechnet. +Dies kann jetzt erweitert werden für die Berechnung des kleinsten +gemeinsamen Vielfachen. + +\begin{beispiel} +Die Berechnungstabelle nur für die Spalten $e_k$ und $f_k$ ergibt +\begin{center} +\renewcommand{\arraystretch}{1.4} +\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} +\hline +k& q_k& e_k& f_k\\ +\hline + & & 0& 1\\ +0& 1& 1& 0\\ +1&-\frac13X-\frac13& 1& 1\\ +2& \frac34X+\frac34& -\frac13X+\frac23& -\frac13X-\frac13\\ + & &-\frac14X^2+\frac14X+\frac32&-\frac14X^2-\frac12X+\frac34\\ +\hline +\end{tabular} +\end{center} +Daraus kann man ablesen, dass +\[ +u += +-\frac14X^2+\frac14X+\frac32 +\qquad\text{und}\qquad +v += +-\frac14X^2-\frac12X+\frac34. +\] +Daraus ergibt sich das kleinste gemeinsame Vielfache auf zwei verschiedene Weisen: +\[ +\operatorname{ggT}(a,b) += +\left\{ +\begin{aligned} +\textstyle +(-\frac14X^2+\frac14X+\frac32)&\cdot(X^4 - 2X^3 -7 X^2 + 8X + 12) +\\ +\textstyle +(-\frac14X^2-\frac12X+\frac34)&\cdot(X^4 + X^3 -7X^2 -X + 6) +\end{aligned} +\right\} += +-\frac14X^6+\frac72X^4-\frac{49}4X^2+9. +\] +Die beiden Berechnungsmöglichkeiten stimmen wie erwartet überein. +\end{beispiel} + +\subsubsection{Anwendung: Decodierung des Reed-Solomon-Codes} +Der Reed-Solomon-Code verwendet Polynome zur Codierung der Daten, +dies wird in Kapitel~\ref{chapter:reedsolomon} im Detail beschrieben. +Bei der Decodierung muss der Faktor $u$ für zwei gegebene Polynome +$n(X)$ und $r(X)$ bestimmt werden. +Allerdings ist das Polynom $r(X)$ nicht vollständig bekannt, nur die +ersten paar Koeffizienten sind gegeben. +Dafür weiss man zusätzlich, wieviele Schritte genau der Euklidische +Algorithmus braucht. +Daraus lässt sich genügend Information gewinnen, um die Faktoren $u$ +und $v$ zu bestimmen. +Das Video \url{https://youtu.be/uOLW43OIZJ0} von Edmund Weitz +erklärt die Theorie hinter dieser Teilaufgabe anhand von Beispielen. + +\begin{beispiel} +Wir berechnen also die Faktoren $u$ und $v$ für die beiden Polynome +\begin{align*} +n(X) +&= +X^{12}+12 +\\ +r(X) +&= +7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + w(X) +\end{align*} +in $\mathbb{F}_{13}[X]$, wobei $w(X)$ ein unbekanntes Polynom vom Grad $5$ ist. +Man weiss zusätzlich noch, dass der euklidische Algorithmus genau drei +Schritte braucht, es gibt also genau drei Quotienten, die in die +Berechnung der Zahlen $e_k$ und $f_k$ einfliessen. +Im ersten Schritt des euklidischen Algorithmus ist der Quotient +$n(X) / r(X)$ zu bestimmen, der Grad $1$ haben muss. +\begin{align*} +a_0=n(X) &= X^{12}+12 +\\ +b_0=r(X) &= 7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + \dots +\\ +q_0 &= 2X+10 +\\ +r_0 = a_0-b_0\cdot q_0 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots +\\ +a_1 &= 7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + \dots +\\ +b_1 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots +\\ +q_1 &= 2X+2 +\\ +r_1 = a_1 - b_1q_1 &= 5X^9 + 10 X^8 + \dots +\\ +a_2 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots +\\ +b_2 &= 5X^9 + 10 X^8 + \dots +\\ +q_2 &= 2X+10 +\end{align*} +Aus den Polynomen $q_k$ können jetzt die Faktoren $u$ und $v$ +bestimmt werden: +\begin{center} +\begin{tabular}{|>{$}c<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} +\hline +k& q_k& e_k& f_k\\ +\hline + & & 0& 1\\ +0& 2X+10& 1& 0\\ +1& 2X+2 & 2X+10& 1\\ +2& 2X+10& 4X^2+11X+8& 2X+2\\ + & & 8X^3+10X^2+11X+12& 4X^2+11X+8\\ +\hline +\end{tabular} +\end{center} +Die Faktorisierung des Polynoms +\[ +u += +8X^3+10X^2+11X+12 +\] +kann bestimmt werden, indem man alle Zahlen $1,2,\dots,12\in\mathbb{F}_{13}$ +einsetzt. +Man findet so die Nullstellen $3$, $4$ und $8$, also muss das Polynom +$u$ faktorisiert werden können als +\[ +u= +8(X-3)(X-4)(X-8) += +8X^3 - 120X^2+544X-768 += +8X^3 +10X^2+11X+12. +\qedhere +\] +\end{beispiel} diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex index fbacba6..2f8117e 100644 --- a/buch/chapters/30-endlichekoerper/galois.tex +++ b/buch/chapters/30-endlichekoerper/galois.tex @@ -27,7 +27,7 @@ Primzahlpotenz $p^n$ von Elementen haben und die die Basis wichtiger kryptographischer Algorithmen sind. % -% Arithmetik module $o$ +% Arithmetik modulo $o$ % \subsection{Arithmetik modulo $p$ \label{buch:subsection:arithmetik-modulo-p}} @@ -413,7 +413,7 @@ Elemente. \begin{figure} \centering \includegraphics{chapters/30-endlichekoerper/images/binomial2.pdf} -\caption{Binomialkoeffizienten module $2$ im Pascal-Dreieck. +\caption{Binomialkoeffizienten modulo $2$ im Pascal-Dreieck. Auf den rot hinterlegten Zeilen, die zu Exponenten der Form $2^k$ gehören, sind alle Koeffizienten ausser dem ersten und letzten durch $2$ teilbar. \label{buch:endliche-koerper:fig:binomial2}} @@ -423,7 +423,7 @@ sind alle Koeffizienten ausser dem ersten und letzten durch $2$ teilbar. \begin{figure} \centering \includegraphics{chapters/30-endlichekoerper/images/binomial5.pdf} -\caption{Binomialkoeffizienten module $5$ im Pascal-Dreieck. +\caption{Binomialkoeffizienten modulo $5$ im Pascal-Dreieck. Die von $0$ verschiedenen Reste werden durch Farben dargestellt: $1=\text{schwarz}$, $2=\text{\color{farbe2}rot}$, diff --git a/buch/chapters/30-endlichekoerper/rechnungen/rs.maxima b/buch/chapters/30-endlichekoerper/rechnungen/rs.maxima new file mode 100644 index 0000000..9116023 --- /dev/null +++ b/buch/chapters/30-endlichekoerper/rechnungen/rs.maxima @@ -0,0 +1,29 @@ +n: X^12 + 12; +r: 7*X^11 + 4*X^10 + X^9 + 12*X^8 + 2*X^7 + 12*X^6; + +q0: 2*X+10; +q1: 2*X+2; +q2: 2*X+10; + +a0: n; +b0: r; +r0: expand(a0 - q0 * b0); + +a1: b0; +b1: r0; +r1: expand(a1 - q1 * b1); + +a2: b1; +b2: r1; +r2: expand(a2 - q2 * b2); + +K: matrix([1,0],[0,1]); + +K: expand(K . matrix([q0,1],[1,0])); +K: expand(K . matrix([q1,1],[1,0])); +K: expand(K . matrix([q2,1],[1,0])); + +u: 8*X^3+10*X^2+11*X+12; +v: 4*X^2+11*X+8; + +factor(u), modulus:13; diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index 02429dc..600336c 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -731,7 +731,7 @@ dass 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 +Das Polynom $a$, reduziert modulo $m$, ist also die multiplikative Inverse von $f$. Bei der praktischen Durchführung des euklidischen Algorithmus ist der diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex index 44eb6bb..dcc31b8 100644 --- a/buch/chapters/90-crypto/arith.tex +++ b/buch/chapters/90-crypto/arith.tex @@ -91,7 +91,7 @@ Die Berechnung der Quadratwurzel lässt sich in Hardware effizient implementieren. \begin{algorithmus} -Der folgende Algorithmsu berechnet $a^k$ in $O(\log_2(k))$ +Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$ Multiplikationen \begin{enumerate} \item Initialisiere $p=1$ und $q=a$ |