\documentclass[12pt,a4paper,german]{article}
\usepackage{url}
%\usepackage{graphics}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{pifont}
\usepackage{ngerman}
\usepackage{float}
\usepackage{diagbox}
\usepackage[latin1]{inputenc}
\usepackage{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{delarray}
% \usepackage{minted}
\usepackage{csquotes}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{longtable}
\usepackage{paralist}
\geometry{left=2.0cm,textwidth=17cm,top=3.5cm,textheight=23cm}

\graphicspath{.}

%%%%%%%%%% Fill out the the definitions %%%%%%%%%
\def \name {Valentin Brandl}					%
\def \matrikel {108018274494}				%
% \def \pname {Vorname2 Nachname2}				%
% \def \pmatrikel {Matrikelnummer2}				%
\def \gruppe {Gruppe 193}					%
\def \uebung {7}								%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 % DO NOT MODIFY THIS HEADER
\newcommand{\hwsol}{
\vspace*{-2cm}
\noindent \matrikel \quad \name \hfill Gruppe:\gruppe \\
% \noindent \pmatrikel \quad \pname \\
\begin{center}{\Large \bf L\"osung f\"ur \"Ubung \# \uebung}\end{center}
}

\newcommand{\cmark}{\ding{51}}%
\newcommand{\xmark}{\ding{55}}%
\newcommand{\csquare}{\text{\rlap{$\checkmark$}}\square}%

\begin{document}
%Import header
\hwsol

\section*{Aufgabe 1}

$P(x) = x^4 + x + 1$ und $grad(P(X)) = 4$

\begin{enumerate}[a)]

    \item $GF(2) = GF(2^1)$. Maximaler Grad von $G(p^m)$ ist $(m-1)$, maximaler Grad von $GF(2^1)$ ist also $1-1=0$, es
        sind also nur die polynome $a_1(x) = 0$ und $a_2(x) = 1$ möglich. Beide haben einen Grad $< 4$, also gibt es $2$
        Polynome in $GF(2)$, deren Grad kleiner ist, als $grad(P(x))$.

    \item $GF(p^n)$: Alle $a_i$ des Polynoms sind Elemente der Menge $A = \{0,1,...,p-1\} \Rightarrow |A| = p$. Jedes
        Polynom besteht aus $n$ Koeffizienten, daher hat hat $GF(p^n)$ genau $p^n$ mögliche Polynome. Da der Grad der
        Polynome $< 4$ sein soll, muss $n$ also $\leq 4$ sein. Abhängig von $p$ sind also $4$ mögliche Werte für $n$
        denkbar, sodass der Grad $< 4$ bleibt

        \begin{tabular}{|c|c|}
            \hline
            $n$ & \# Polynome \\\hline
            1 & $p$ \\\hline
            2 & $p^2$ \\\hline
            3 & $p^3$ \\\hline
            4 & $p^4$ \\\hline
        \end{tabular}

\end{enumerate}


\section*{Aufgabe 2}

\begin{tabular}{|c||c|c|c|c|c|c|c|c|}
    \hline
    $\cdot$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline\hline
    0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\hline
    1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline
    2 & 0 & 2 & 4 & 6 & 5 & 7 & 1 & 3 \\\hline
    3 & 0 & 3 & 6 & 5 & 1 & 2 & 7 & 4 \\\hline
    4 & 0 & 4 & 5 & 1 & 7 & 3 & 2 & 5 \\\hline
    5 & 0 & 5 & 7 & 2 & 3 & 6 & 4 & 3 \\\hline
    6 & 0 & 6 & 1 & 7 & 2 & 4 & 6 & 5 \\\hline
    7 & 0 & 7 & 3 & 4 & 5 & 3 & 5 & 2 \\\hline
\end{tabular}


\section*{Aufgabe 3}

$P(x) = x^8 + x^4 + x^3 + x + 1$

\begin{enumerate}[a)]

    \item
        \begin{align*}
            A(x) &= x^7 + x^6 + x^4 + x^2 + x + 1 \\
            B(x) &= x^2 + x \\
            A(x) * B(x) &= x^9+x^7+x^5+x^4+x \equiv x^7+x^2+1 &\mod P(x) \\
                        &= 0x85
        \end{align*}

    \item
        \begin{align*}
            A(x) &= x^4 + x^2 + x + 1 \\
            B(x) &= x^4 + 1 \\
            A(x) * B(x) &= x^8 + x^6 + x^5 + x^2 + x + 1 \equiv x^6 + x^5 + x^4 + x^3 + x^2 &\mod P(x) \\
                        &= 0x7C
        \end{align*}

    \item
        \begin{align*}
            A(x) &= x^6 + x^5 + x^2 + x \\
            B(x) &= x^2 + x + 1 \\
            A(x) * B(x) &= x^5 + x^4 + x &\mod P(x) \\
                        &= 0x32
        \end{align*}

\end{enumerate}


\section*{Aufgabe 4}

Die multiplikativen Inversen wurden aus der Tabelle 4.2 im Buch abgelesen.

$P(x) = x^8 + x^4 + x^3 + x + 1$

\begin{enumerate}[a)]

    \item
        \begin{align*}
            A(x) &= x^5 + x^4 + x^3 + x^2 \\
            B(x) &= x^5 + x^2 + 1 \widehat{=} 0x25 \\
            B^{-1}(x) &= 0x4D \widehat{=} x^6 + x^3 + x^2 + 1 \\
            A(x) \div B(x) &= A(x) * B^{-1}(x) = \\
                           &= x^{11} + x^{10} + x^9 + x^7 + x^5 + x^3 \equiv x^5 + x^3 + x &\mod P(x) \\
                           &\widehat{=} 0x2A
        \end{align*}

    \item
        \begin{align*}
            A(x) &= x^7 + x^2 + x + 1 \\
            B(x) &= x^6 + x^4 + x^3 + x^2 \widehat{=} 0x5C \\
            B^{-1}(x) &= 0x51 \widehat{=} x^6 + x^4 + 1 \\
            A(x) \div B(x) &= A(x) * B^{-1}(x) = \\
                           &= x^{13} + x^{11} + x^8 + x^5 + x^4 + x^2 + x + 1 \equiv x^7 + x^5 + x^4 + x^3 + 1 &\mod
                           P(x) \\
                           &\widehat{=} 0xB9
        \end{align*}

\end{enumerate}


\section*{Aufgabe 5}

$P(x) = x^4 + x^2 + 3x + 5$

\begin{enumerate}[a)]

    \item
        \begin{tabular}{|c||c|c|c|c|c|c|c|}
            \hline
            $+$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline\hline
            0 & 0 & 1 & 2 & 3 & 4 & 4 & 6 \\\hline
            1 & 1 & 2 & 3 & 4 & 5 & 6 & 0 \\\hline
            2 & 2 & 3 & 4 & 5 & 6 & 0 & 1 \\\hline
            3 & 3 & 4 & 5 & 6 & 0 & 1 & 2 \\\hline
            4 & 4 & 5 & 6 & 0 & 1 & 2 & 3 \\\hline
            5 & 5 & 6 & 0 & 1 & 2 & 3 & 4 \\\hline
            6 & 6 & 0 & 1 & 2 & 3 & 4 & 5 \\\hline
        \end{tabular}

    \item
        \begin{tabular}{|c||c|c|c|c|c|c|c|}
            \hline
            $\cdot$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline
            0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\hline
            1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline
            2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\\hline
            3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 \\\hline
            4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \\\hline
            5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\\hline
            6 & 0 & 6 & 5 & 4 & 3 & 2 & 1 \\\hline
        \end{tabular}

    \item
        \begin{enumerate}[i)]
            \item
                \begin{align*}
                    A(x) &= 3x^2 + x + 2 \\
                    B(x) &= 6x^4 + 4x^2 + 3x + 5 \\
                    A(x) + B(x) &= 6x^4 + 4x &\mod P(x)
                \end{align*}

            \item Nein, da $A(x) + B(x)$ auch ohne die Moduloreduktion keinen Koeffizienten mit einem Grad $> 6$ hat
        \end{enumerate}

    \item
        \begin{enumerate}[i)]
            \item
                \begin{align*}
                    A(x) &= 3x^3 + x + 2 \\
                    B(x) &= 6x^3 + 4x^2 + 3x + 5 \\
                    A(x) - B(x) &= 4x^3 + 3x^2 + 5x + 4 &\mod P(x)
                \end{align*}

                \item Nein, da $A(x) - B(x)$ auch ohne die Moduloreduktion keinen Koeffizienten mit einem Grad $> 6$ hat
        \end{enumerate}

    \item
        \begin{enumerate}[i)]
            \item
                \begin{align*}
                    A(x) &= 5x^4 + x + 2 \\
                    B(x) &= 3x^3 + 5x^2 + 4 \\
                    A(x) * B(x) &= x^7 + 4x^6 + 2x^4 + 4x^3 + 3x^2 + 4x + 1 &\mod P(x) \\
                                &\equiv 2x^3 + 5x^2 + 3x + 5 &\mod P(x)
                \end{align*}

            \item
                \begin{align*}
                    A(x) &= x^3 + 2x + 4 \\
                    B(x) &= 4x^4 + 6x^3 + 3 \\
                    A(x) * B(x) &= 4x^7 + 6x^6 + 6x^5 + 6x^3 + 6x + 5 &\mod P(x) \\
                                &\equiv x^3 + 3x^2 + x + 4 &\mod P(x)
                \end{align*}
        \end{enumerate}

    \item
        \begin{align*}
            x^4 &\equiv 6x^2 + 4x + 2 &\mod P(x) \\
            x^5 &\equiv 6x^3 + 4x^2 + 2x &\mod P(x) \\
            x^6 &\equiv 4x^3 + x^2 + 5x + 5 &\mod P(x) \\
            x^7 &\equiv 3x^3 + 6x^2 + 1 &\mod P(x) \\
        \end{align*}

\end{enumerate}


\end{document}

