\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm} %these packages let you use standard math symbols etc.
\usepackage{color}
\usepackage{enumitem}
\usepackage{geometry}
\setlist{nosep}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}
\newcommand{\ZZ}{\mathbb{Z}}
\title{\vspace{-5em}Coding and Cryptography Fall 2016\\ Mission \#7\\ Due Friday, November 4th}
\author{Katherine E. Stange}
\date{\today}
\begin{document}
\maketitle %this is what makes the title from the data above
{\color{red}
Note: This is an individual mission. You may meet with group members (optionally) if you'd like to give each other feedback and help, or collaborate on creating proofs.
Overview:
\begin{enumerate}
\item The goal of this Mission is to write the textbook chapter on finite fields, including some example problems. I have given a suggested outline below.
\item It is crucial that you cite resources. If you collaborate with someone on a proof or problem, you should cite them there (a simple ``Collaborated with so-and-so.'' will suffice). If you use internet or book resources (including our own textbook) in any way, cite them and explain how (e.g., read the webpage (give URL) to get background information). This is very important. Everything you write must be intellectually your own property, even if you learned the method somewhere else. Cite where you learned the method and then write {\bf after} not {\bf during} your interaction with the resource.
\item In class I'll arrange working pairs for those who wish to collaborate or give feedback with other people in the class.
\item I will grade on whether, as a publisher, I would be happy with this as a textbook chapter in a textbook aimed at students in this course.
\end{enumerate}
The rest of this document serves as a template for the chapter. Please remove anything in red in this document, and replace with appropriate material as explained.
}
\section{Introduction}
{\color{red}
Give a couple of sentences of introduction saying what we will be studying (in a general way -- what type of thing is it?) and why. We will use finite fields when we study coding theory and in a brief introduction to elliptic curve cryptography, among other things.
}
\section{What is a field?}
{\color{red}
Explain in general terms what a ring and field are.
}
\subsection{The fields axioms}
{\color{red}
Then give the field axioms (you can steal them from the worksheets directly if you want).
}
\subsection{Common examples}
{\color{red}
Give common examples of fields and non-fields, e.g. which of the real numbers, complex numbers, rationals, integers, etc. are fields? Explain why or why not.
}
\subsection{When is $\ZZ/n\ZZ$ a field?}
{\color{red}
Remind the reader that $\ZZ/n\ZZ$ is a ring, and explain under what circumstance it is a field. Explain exactly what goes wrong when it is not, and why. Give examples to illustrate the point, showing explicitly what goes wrong or not.
}
\section{Finite fields from polynomials}
{\color{red}
The purpose of this section is to give an explanation of how to generate a ring $(\ZZ/n\ZZ)[X]/(f(X))$ using a modulus $n$ and a polynomial modulus $f(X)$. First, define the polynomial ring $(\ZZ/n\ZZ)[X]$ as the collection of polynomials with coefficients in $\ZZ/n\ZZ$. Give examples. How many elements does this ring have? Then, define the ring $(\ZZ/n\ZZ)[X]/(f(X))$ by further working modulo $f(X)$. Tell me exactly what the elements are, and how to combine them with addition and multiplication (i.e. what are the rules for working in the ring? give examples). State a theorem about how many elements this ring has, and write a nice proof.
}
\subsection{The field of four elements}
{\color{red}
Use this method to create $\mathbb{F}_4$, and show its addition, subtraction, multiplication and division tables. Point out why it is a field, and not just a ring.
}
\subsection{When is $(\ZZ/n\ZZ)[X]/(f(x))$ a field?}
{\color{red}
First, define what it means for a polynomial of $(\ZZ/n\ZZ)[X]$ to be irreducible. Give examples and non-examples, with justification.
State a theorem demonstrating that $(\ZZ/n\ZZ)[X]/(f(X))$ is a field if and only if $n$ is prime and $f(X)$ is irreducible. Prove the `only if' direction.
}
\subsection{Examples}
{\color{red}
Generate a novel example of a finite field (not one you've seen anywhere else).
}
\subsection{Finding inverses}
{\color{red}
Explain that it is possible to find inverses using the Euclidean algorithm, just as one does in modular arithmetic. Demonstrate the process with a novel example (not one you've seen anywhere else).
}
\section{Some example problems}
{\color{red}
The purpose of this section is to give students some practice problem examples. Give nicely written, completely justified and explanatory solutions, much as you would hope to find in a textbook.
\begin{enumerate}
\item Determine the complete list of irreducible polynomials of degree at most $3$ working with coefficients modulo $2$. Explain your method.
\item For any field $K$, we write $K^*$ for its invertible elements, i.e. everything except $0$. For the field $(\ZZ/2\ZZ)[X]/(X^2 + X + 1)$, find a multiplicative generator of $K^*$. Justify.
\item Diffie-Hellman Key Exchange could be performed with any finite field, if it has a multiplicative generator for its invertible elements. Give a concrete example demonstration over a finite field of nine elements, with concrete elements, i.e. pick Alice and Bob's secrets, etc.
\item How many elements does a $5$-dimensional vector space over $\mathbb{F}_9$, the field of nine elements, have? Justify.
\end{enumerate}
}
\end{document}