\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.