\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage{cancel}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage{multicol}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}


\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

\newcommand{\hl}[1]{%
  \colorbox{red!50}{$\displaystyle#1$}}            
            
\input{preamble.tex}

\begin{document}

\homework{17: Elliptic Curves over Finite Fields}{Due Friday, Week 10}

Solve \textbf{three} of the following \textbf{six} problems.    As always, prove your claims/have fun! 


\begin{enumerate}
\item Consider the following three elliptic curves over $\mathbb{F}_5 = \mathbb{Z} / 5\mathbb{Z}$.
\begin{itemize}
\item $y^2 = x^3 - x + 1$,
\item $y^2 = x^3 -4x + 2$,
\item $y^2 = x^3 + 2x$.
\end{itemize}
For each curve, draw the collection of all of its points.  (Use separate plots for each curve, as it will be hard to distinguish two of the same curve.)
\item Choose any elliptic curve $E$ in $\mathbb{F}_7[x] = (\mathbb{Z}/7\mathbb{Z})[x]$, and throw in the point at infinity $\mathcal{O}$.  Find the group corresponding to this curve!
\item Recall, from earlier in the quarter, the following definition: in a group $\langle  G, + \rangle$, an element $g$ is said to \textbf{generate} that group if we can write any element in the group as just a repeated sum of $g$'s.  For example, $\langle \mathbb{Z}/4\mathbb{Z}, + \rangle$ is generated by the element 1, because we can write $1+1 = 2, 1+1+1 = 3, 1+1+1+1 = 4 \cong 0 \mod 4$.
\begin{enumerate}
\item Find an elliptic curve that is generated by one element.
\item Find an elliptic curve that is not generated by any one element.
\end{enumerate}
\item What is the maximum number of points an elliptic curve over $\mathbb{Z} / 5\mathbb{Z}$ can contain?  What is the minimum?
\item \begin{enumerate}
\item Create a finite field of order 9 using the methods described in class.  (That is: find an irreducible polynomial $p(t)$ of degree 2 in $\mathbb{F}_3[t] =  (\mathbb{Z}/3\mathbb{Z})[t]$, and then look at $\mathbb{F}_3[t]/p(t)$.)  Call this field $\mathbb{F}_9$.
\item Consider the elliptic curve $E$ given by all of the points $(x,y) \in \mathbb{F}_9$ that satisfy the equation $y^2 = x^3 + 2x + 2$.  Find all of the points in $E$. 
\item  Add in a point at infinity $\mathcal{O}$ to $E$, and form the group table given by adding points in $E \cup \{\mathcal{O}\}$ together.
\end{enumerate}
\item In class, we claimed that our elliptic curve operations were well-defined over the finite fields.  Prove this!  Namely, show that if $E$ is an elliptic curve, then
\begin{itemize}
\item If $P$, $Q$ are two distinct points on $E$ and the line $L$ through $P, Q$ is not tangent to $E$ at either $P, Q$, then either $L$ is a vertical line or there is a unique third point of intersection $R \neq P, Q$ between our line and our curve.
\item If $P$ is any point on the curve $E$ and $L$ is the tangent to $E$ through $P$, then either $L$ is vertical, $L$ goes through $E$ at exactly one other point $R$, or $P$ is a ``triple-tangent:'' that is, if we write $L: y=mx+c, E: x^3 - ax +b, P = (r,s)$, we have that $x^3 - ax + b - (mx+c)^2 = (x-r)^3$.
\end{itemize}
\end{enumerate}

\end{document}