75 lines
4.9 KiB
TeX
75 lines
4.9 KiB
TeX
\chapter{Endliche Körper $\mathbb{F}_{p^n}$}\label{endliche Körper}
|
|
$\mathbb{F}_p:=\mathbb{Z}_p$ ($p$ ist eine Primzahl) ist ein Körper.
|
|
Zudem können Körper auch für beliebige Primzahlpotenzen $p^n$ mit $n\in\mathbb{N},n>0$ mithilfe der Polynome aus $\mathbb{F}_p$ vom Grad $<n$ konstruiert werden:
|
|
$$\begin{aligned}
|
|
\mathbb{F}_{p^n}:=&\{a(x)\mid a(x)\in\mathbb{F}_p[x],\text{grad}(a(x))<n\}\\
|
|
=&\{a_{n-1}x^{n-1}+...+a_1x+a_0\mid a_i\in\mathbb{F}_p\}
|
|
\end{aligned}$$
|
|
Die normale Polynomaddition stellt bereits eine Addition in $\mathbb{F}_{p^n}$ dar.
|
|
Die normale Polynommultiplikation ist allerdings in $\mathbb{F}_{p^n}$ nicht abgeschlossen.
|
|
Das heißt es gibt häufig Produkte mit Polynomen vom Grad $>n$.
|
|
Hierbei lässt sich allerdings analog zu $\mathbb{Z}$ (siehe \ref{Der Ring Z}) durch eine Polynomdivision mit Rest durch $p(x)$ ein Wert in $\mathbb{F}_{p^n}$ erzeugen.
|
|
|
|
\section{Polynomdivision mit Rest}
|
|
Ist $\mathbb{F}$ ein Körper und $a(x),b(x)\in\mathbb{F}[x],b(x)\ne0$, so gibt es eindeutig bestimmte Polynome $q(x),r(x)\in\mathbb{F}$ mit:
|
|
$$a(x)=b(x)\cdot q(x)+r(x)\text{ und } 0\le\text{grad}(r(x))<\text{grad}(b(x))$$
|
|
Alternativ wird für den Rest $r(x)$ auch \say{$a(x) \mod b(x)=r(x)$} geschrieben.
|
|
|
|
\section{Berechnung der Inversen}
|
|
Der größte gemeinsame Teiler (das Polynom mit den höchsten Grad, dass $a(x)$ und $b(x)$ teilt) kann mithilfe des Euklid'schen Algorithmus (siehe \ref{euklid}) berechnet werden.
|
|
Ist $\mathbb{F}_{p^n}$ bezüglich eines irreduziblen Polynoms $p(x)$ definiert,
|
|
lässt sich mithilfe der Anwendung des erweiterten Euklid'schen Algorithmus (siehe \ref{erweiterter Euklid}) auf die Polynome $a(x)$ und $b(x)$ eine Inverse von $a(x)$ in $\mathbb{F}_{p^n}$ bestimmen.
|
|
|
|
\section{$\mathbb{F}_2$}
|
|
Ein Polynom von Grad $n$ ist durch die Folge von $n+1$ Koeffizienten $a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$ eindeutig definiert.
|
|
Bei Polynomen aus $\mathbb{F}_2[x]$ ergibt dies eine Bitfolge.
|
|
|
|
\subsection{Irreduzible Polynome über $\mathbb{F}_2$}
|
|
\begin{itemize}
|
|
\item Polynome von Grad 1 (lineare Polynome) sind immer irreduziblen.
|
|
Für $\mathbb{F}_2$ sind dies:
|
|
$$\begin{aligned}
|
|
p_{1,1}(x)=&x\\
|
|
p_{1,2}(x)=&x+1
|
|
\end{aligned}$$
|
|
|
|
\item Es gibt in $\mathbb{F}_2$ 4 paarweise verschiedene Polynome von Grad 2.
|
|
3 davon haben eine Nullstelle und lassen sích daher in Linearfaktoren zerlegen.
|
|
Das einzige irreduzible Polynom von Grad 2 ist:
|
|
$$p_2(x)=x^2+x+1$$
|
|
\item Ein Polynom von Grad 3 ist genau dann irreduzible, falls $p(x)$ keine Nullstellen hat.
|
|
Dies trifft für die folgenden zwei Polynome zu:
|
|
$$\begin{aligned}
|
|
p_{3,1}(x)=&x^3+x+1\\
|
|
p_{3,2}(x)=&x^3+x^2+1\\
|
|
\end{aligned}$$
|
|
\item Ein Polynom von Grad 4 ist genau dann irreduzible, wenn $p(x)$ keine Nullstelle hat und auch nicht das Quadrat von $p_2(x)$ ($x^4+x^2+1$) ist:
|
|
$$\begin{aligned}
|
|
p_{4,1}(x)=&x^4+x+1\\
|
|
p_{4,1}(x)=&x^4+x^3+1\\
|
|
p_{4,1}(x)=&x^4+x^3+x^2+x+1\\
|
|
\end{aligned}$$
|
|
\end{itemize}
|
|
|
|
\subsubsection{Irreduzibilität von $m(x)=x^8+x^4+x^3+x+1\in\mathbb{F}_2[x]$}
|
|
Das Polynom, welches die MixColumns()-Substitution im AES (siehe \ref{aes}) definiert ist auf die Irreduzibilität zu überprüfen.
|
|
Falls $m(x)$ reduzibel wäre, gebe es einen irreduziblen Faktor $d(x)$ für den gilt:
|
|
$$\text{grad}(d(x))\in\{1,2,3,4\}$$
|
|
\vspace{2mm}
|
|
Nun werden die verschiedenen Grade untersucht:
|
|
\begin{enumerate}
|
|
\item es gibt keinen linearen Faktor, da $m(0)=m(1)=1\ne 0$
|
|
\item eine Polynomdivision mit $p_2(x)$ ergibt $d(x)\mod p_2(x)=x+1\ne 0$
|
|
\item die Polynomdivisionen mit den irreduziblen Polynomen vom Grad 3 ergeben:
|
|
$$\begin{aligned}
|
|
m(x)\mod p_{3,1}=&x^2\\
|
|
m(x)\mod p_{3,2}=&x+1\\
|
|
\end{aligned}$$
|
|
\item die Polynomdivisionen mit den irreduziblen Polynomen vom Grad 4 ergeben:
|
|
$$\begin{aligned}
|
|
m(x)\mod p_{4,1}=&x^3+x^2+1\\
|
|
m(x)\mod p_{4,2}=&x^3+x^2\\
|
|
m(x)\mod p_{4,3}=&x^3+x^2\\
|
|
\end{aligned}$$
|
|
\end{enumerate}
|
|
Da es keinen irreduziblen Faktor $d(x)$ gibt ist $m(x)=x^8+x^4+x^3+x+1$ selbst irreduzibel. |