\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}
\hypersetup{colorlinks=true,urlcolor=blue,citecolor=blue,linkcolor=blue}
\usepackage{courier}
\usepackage{tikz}
\usetikzlibrary{calc,matrix,arrows,decorations.markings}
\usepackage{array}
\usepackage{color}
\usepackage{enumerate}
\usepackage{nicefrac}
\usepackage{listings}
\lstset{
	basicstyle=\small\ttfamily,
	keywordstyle=\color{blue},
	language=python,
	xleftmargin=16pt,
}

\textwidth=5.8in
\textheight=9in
\topmargin=-0.5in
\headheight=0in
\headsep=.5in
\hoffset  -.4in
\pagestyle{empty}

% growing list of useful macros, use these where appropriate and add to this list as needed
\newcommand{\kbar}{\bar{k}}
\newcommand{\Fp}{\mathbb{F}_p}
\newcommand{\Fptwo}{\mathbb{F}_{p^2}}
\newcommand{\Fpbar}{\overline{\mathbb{F}}_p}
\newcommand{\Fq}{\mathbb{F}_q}
\newcommand{\Fqn}{\mathbb{F}_{q^n}}
\newcommand{\Fqbar}{\overline{\mathbb{F}}_q}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Qbar}{\overline{\mathbb{Q}}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\H}{\mathbb{H}}
\newcommand{\D}{\mathbb{D}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ZnZ}{\Z/n\Z}
\newcommand{\M}{\textsf{M}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\Gal}{{\rm Gal}}
\newcommand{\GL}{{\rm GL}}
\newcommand{\PGL}{{\rm PGL}}
\newcommand{\End}{{\rm End}}
\newcommand{\DFT}{{\rm DFT}}
\newcommand{\dy}{\,dy}
\newcommand{\dx}{\,dx}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\kron}[2]{\bigl(\frac{#1}{#2}\bigr)}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\softO}{\widetilde{O}}
\newcommand{\ceil}[1]{\lceil{#1}\frac{1}eil}
\newcommand{\Exp}{{\rm E}}
\newcommand{\K}{\mathcal{K}}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\OK}{\O_K}
\newcommand{\T}{{\rm T}}
\newcommand{\N}{{\rm N}}
\newcommand{\re}{\operatorname{re}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\ord}{{\rm ord}}
\newcommand{\SL}{{\rm SL}}
\newcommand{\PSL}{{\rm PSL}}
\newcommand{\EllO}{{\rm Ell}_\O}
\newcommand{\fraka}{\mathfrak{a}}
\newcommand{\frakb}{\mathfrak{b}}
\newcommand{\frakc}{\mathfrak{c}}
\newcommand{\cl}{{\rm cl}}
\newcommand{\disc}{{\rm disc}}
\newcommand{\abcd}{\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)}
\newcommand{\ABCD}{\left(\begin{smallmatrix}A&B\\C&D\end{smallmatrix}\right)}
\newcommand{\p}{\mathfrak{p}}
\renewcommand{\a}{\mathfrak{a}}
\renewcommand{\b}{\mathfrak{b}}
\newcommand{\Frob}{{\rm Frob}}
\newcommand{\lt}{{\rm lt}}
\newcommand{\id}{{\rm id}}
\newcommand{\sumprime}{\sideset{}{'}\sum}

\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem*{remark}{Remark}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.783 Elliptic Curves\hspace{215pt}Spring~2017}\\\vspace{4pt}
\textbf{Problem Set \#12\hspace{210pt}Due: 05/17/2017}
\normalsize
\begin{picture}(5.8,.1) 
\put(0,0) {\line(1,0){5.8}}
\end{picture}
\end{center}
\vspace{-12pt}

\subsection*{Description}

These problems are related to the material covered in Lectures 23--25.
As usual, the first person to spot each non-trivial typo/error will receive 1--3 points of extra credit.
\medskip

\noindent\textbf{Instructions}: Solve any combination of problems that sums to 150 points.
Then complete Problem~9, which is a survey.
Your solutions are to be written up in latex and submitted as a pdf-file with a filename of the form \texttt{SurnamePset12.pdf} via e-mail to \texttt{drew@math.mit.edu} \textbf{prior to the start of class on 5/17}.  This \href{https://cloud.sagemath.com/projects/bec670ef-3089-49ad-a790-f587e6579df9/files/18.783%20Problem%20Set%2012.sagews}{Sage worksheet} contains modular polynomials and helper functions from previous problem sets that you may find useful.

\subsection*{Problem 1. Isogeny volcanoes (100 points)}

For the purposes of this problem, an isogeny volcano is an ordinary component of an $\ell$-isogeny graph $G_\ell(\Fq)$ that does not contain $0$ or $1728$, where $\ell\nmid q$.
This is a bi-directed graph that we regard as an undirected graph.

\begin{enumerate}[{\bf (a)}]
\item Use the CM method to explicitly construct isogeny volcanoes that meet each of the following sets of criteria:
\begin{enumerate}[{\bf(i)}]
\item $\ell=2$, $d=3$, $V_0$ is a 5-cycle;
\item $\ell=3$, $d=2$, $V_0$ contains a single edge;
\item $\ell=7$, $d=1$, $V_0$ contains a single vertex with two self-loops.
\end{enumerate}
In your answers, specify the finite field used, the discriminant of the order $\O_0$ corresponding to $V_0$, and list each bi-directed edge just once, as a pair $(v_1,v_2)$ of $j$-invariants corresponding to a horizontal or descending edge.
\item Use the CM method to construct a single ordinary elliptic curve $E/\Fq$ that simultaneously satisfies all of the following criteria:
\begin{enumerate}[{\bf (i)}]
\item $j(E)$ is on the floor of its $2$-volcano, which has depth 6.
\item $j(E)$ is on the surface of its $3$-volcano, which has depth 3.
\item $j(E)$ is on the middle level of its $5$-volcano, which has depth 2.
\item $j(E)$ is on the floor of its $7$-volcano, which has depth 5.
\item $j(E)$ is one of exactly two vertices in its $11$-volcano.
\item $j(E)$ is the only vertex in its $13$-volcano.
\end{enumerate}
In your answer, specify the finite field $\Fq$, the $j$-invariant $j(E)$, and the discriminant~$D$ of the order $\O\simeq\End(E)$.

\item
Prove that the cardinality of a $2$-isogeny volcano with an odd number of vertices must be a Mersenne number (an integer of the form $2^n-1$).  Give an explicit example of a $2$-isogeny volcano with 15 vertices.
\item
Prove that every ordinary elliptic curve $E/\Fq$ is isogenous to an elliptic curve $E'/\Fq$ for which $E'(\Fq)$ is a cyclic group.
\end{enumerate}

\subsection*{Problem 2. Computing modular polynomials (100 points)}
As we have seen, the modular polynomials $\Phi_\ell(X,Y)$ play a key role in many theoretical and practical applications of elliptic curves.
One can compute them using the $q$-expansions of the modular functions $j(z)$ and $j(\ell z)$, but this is approach is difficult to implement efficiently and extremely memory intensive.
In this problem you will implement a more efficient algorithm that uses isogeny volcanoes.
The strategy is to use a CRT approach, working modulo primes $p$ that are carefully selected to achieve a configuration of $\ell$-volcanoes similar to that depicted below:

\vspace{6pt}
\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}
\draw (-4.5,0) ellipse (1 and 0.1);
\draw (-1.5,0) ellipse (1 and 0.1);
\draw (1.5,0) ellipse (1 and 0.1);
\draw (-4.5,0.1) -- (-4.6,-0.06);
\draw (-4.5,0.1) -- (-4.56,-0.06);
\draw (-4.5,0.1) -- (-4.52,-0.06);
\draw (-4.5,0.1) -- (-4.48,-0.06);
\draw (-4.5,0.1) -- (-4.44,-0.06);
\draw (-4.5,0.1) -- (-4.4,-0.06);
\draw[fill=red] (-4.5,0.1) circle (0.04);
\draw (-1.5,0.1) -- (-1.6,-0.05);
\draw (-1.5,0.1) -- (-1.56,-0.05);
\draw (-1.5,0.1) -- (-1.52,-0.05);
\draw (-1.5,0.1) -- (-1.48,-0.05);
\draw (-1.5,0.1) -- (-1.44,-0.05);
\draw (-1.5,0.1) -- (-1.4,-0.05);
\draw[fill=red] (-1.5,0.1) circle (0.04);
\draw (1.5,0.1) -- (1.6,-0.05);
\draw (1.5,0.1) -- (1.56,-0.05);
\draw (1.5,0.1) -- (1.52,-0.05);
\draw (1.5,0.1) -- (1.48,-0.05);
\draw (1.5,0.1) -- (1.44,-0.05);
\draw (1.5,0.1) -- (1.4,-0.05);
\draw (-5,-0.1) -- (-5.35,-0.7);
\draw[fill=red] (-5.35,-0.7) circle (0.04);
\draw (-5,-0.1) -- (-5.21,-0.7);
\draw[fill=red] (-5.21,-0.7) circle (0.04);
\draw (-5,-0.1) -- (-5.07,-0.7);
\draw[fill=red] (-5.07,-.7) circle (0.04);
\draw (-5,-0.1) -- (-4.93,-0.7);
\draw[fill=red] (-4.93,-0.7) circle (0.04);
\draw (-5,-0.1) -- (-4.79,-0.7);
\draw[fill=red] (-4.79,-0.7) circle (0.04);
\draw (-5,-0.1) -- (-4.65,-0.7);
\draw[fill=red] (-4.65,-0.7) circle (0.04);
\draw[fill=red] (-5,-0.1) circle (0.04);

\draw (-4,-0.1) -- (-4.35,-0.7);
\draw[fill=red] (-4.35,-0.7) circle (0.04);
\draw (-4,-0.1) -- (-4.21,-0.7);
\draw[fill=red] (-4.21,-0.7) circle (0.04);
\draw (-4,-0.1) -- (-4.07,-0.7);
\draw[fill=red] (-4.07,-0.7) circle (0.04);
\draw (-4,-0.1) -- (-3.93,-0.7);
\draw[fill=red] (-3.93,-0.7) circle (0.04);
\draw (-4,-0.1) -- (-3.79,-0.7);
\draw[fill=red] (-3.79,-0.7) circle (0.04);
\draw (-4,-0.1) -- (-3.65,-0.7);
\draw[fill=red] (-3.65,-0.7) circle (0.04);
\draw[fill=red] (-4,-0.1) circle (0.04);

\draw (-2,-0.1) -- (-2.35,-0.7);
\draw[fill=red] (-2.35,-0.7) circle (0.04);
\draw (-2,-0.1) -- (-2.21,-0.7);
\draw[fill=red] (-2.21,-0.7) circle (0.04);
\draw (-2,-0.1) -- (-2.07,-0.7);
\draw[fill=red] (-2.07,-0.7) circle (0.04);
\draw (-2,-0.1) -- (-1.93,-0.7);
\draw[fill=red] (-1.93,-0.7) circle (0.04);
\draw (-2,-0.1) -- (-1.79,-0.7);
\draw[fill=red] (-1.79,-0.7) circle (0.04);
\draw (-2,-0.1) -- (-1.65,-0.7);
\draw[fill=red] (-1.65,-0.7) circle (0.04);
\draw[fill=red] (-2,-0.1) circle (0.04);

\draw (-1,-0.1) -- (-1.35,-0.7);
\draw[fill=red] (-1.35,-0.7) circle (0.04);
\draw (-1,-0.1) -- (-1.21,-0.7);
\draw[fill=red] (-1.21,-0.7) circle (0.04);
\draw (-1,-0.1) -- (-1.07,-0.7);
\draw[fill=red] (-1.07,-0.7) circle (0.04);
\draw (-1,-0.1) -- (-0.93,-0.7);
\draw[fill=red] (-0.93,-0.7) circle (0.04);
\draw (-1,-0.1) -- (-0.79,-0.7);
\draw[fill=red] (-0.79,-0.7) circle (0.04);
\draw (-1,-0.1) -- (-0.65,-0.7);
\draw[fill=red] (-0.65,-0.7) circle (0.04);
\draw[fill=red] (-1,-0.1) circle (0.04);

\draw (1,-0.1) -- (1.35,-0.7);
\draw[fill=red] (1.35,-0.7) circle (0.04);
\draw (1,-0.1) -- (1.21,-0.7);
\draw[fill=red] (1.21,-0.7) circle (0.04);
\draw (1,-0.1) -- (1.07,-0.7);
\draw[fill=red] (1.07,-0.7) circle (0.04);
\draw (1,-0.1) -- (0.93,-0.7);
\draw[fill=red] (0.93,-0.7) circle (0.04);
\draw (1,-0.1) -- (0.79,-0.7);
\draw[fill=red] (0.79,-0.7) circle (0.04);
\draw (1,-0.1) -- (0.65,-0.7);
\draw[fill=red] (0.65,-0.7) circle (0.04);
\draw[fill=red] (1,-0.1) circle (0.04);

\draw (2,-0.1) -- (2.35,-0.7);
\draw[fill=red] (2.35,-0.7) circle (0.04);
\draw (2,-0.1) -- (2.21,-0.7);
\draw[fill=red] (2.21,-0.7) circle (0.04);
\draw (2,-0.1) -- (2.07,-0.7);
\draw[fill=red] (2.07,-0.7) circle (0.04);
\draw (2,-0.1) -- (1.93,-0.7);
\draw[fill=red] (1.93,-0.7) circle (0.04);
\draw (2,-0.1) -- (1.79,-0.7);
\draw[fill=red] (1.79,-0.7) circle (0.04);
\draw (2,-0.1) -- (1.65,-0.7);
\draw[fill=red] (1.65,-0.7) circle (0.04);
\draw[fill=red] (2,-0.1) circle (0.04);

\end{tikzpicture}
\end{center}
\end{figure}
\noindent
Here we have a configuration of three $\ell$-volcanoes, with $\ell=7$, each of depth $d=1$.  There are a total of $\ell+2$ vertices on the surface (any value greater than $\ell+1$ suffices).

Provided we have completely ``mapped" this configuration of $\ell$-volcanoes, meaning that we know the $j$-invariants of every vertex in the figure and the edges between them, we can compute $\Phi_\ell(X,Y)$ as follows.
For any particular $j$-invariant $j_i$ on the surface, we know the values of all the roots of $\phi_i(Y)=\Phi_\ell(j_i,Y)$, since we know the $\ell+1$ neighbors of $j_i$ in $G_\ell(\Fp)$.
We can therefore compute each $\phi_i$ as the product of its linear factors.
If we then consider the coefficient of  $Y^k$ in $\phi_i$, we know (at least) $\ell+2$ values $c_{ik}$ of this coefficient, corresponding to $\ell+2$ distinct $j_i$.  This suffices to uniquely determine the polynomial $\psi_k(X)$ of degree at most $\ell+1$ for which $\psi_k(j_i)=c_{ik}$, via Lagrange interpolation:
\[
\psi_k(X) = \sum_{i=1}^{\ell+2} c_{ik}\prod_{m\ne i}\frac{(X-j_m)}{(j_i-j_m)}
\]

\begin{enumerate}[{\bf (a)}]
\item Prove that $\Phi_\ell(X,Y)=\sum_{k=0}^{\ell+1}\psi_k(X)Y^k$.
\end{enumerate}

To make things simpler, we will use a configuration with (at least) $\ell+2$ isomorphic $\ell$-volcanoes, each with one vertex on the surface and $\ell+1$ neighbors on the floor.
This can be achieved using a fundamental discriminant $D$ with $(\frac{D}{\ell})=-1$ and $h(D)\ge \ell+2$.
The vertex on the surface of each $\ell$-volcano will have endomorphism ring equal to the maximal order for $K=\Q(\sqrt{D})$, and the vertices on the floor will then have endomorphism ring equal to the order $\O'$ with discriminant $\ell^2D$ (note that $\O'$ has index $\ell$ in $\O$).  For convenience, we will choose $D$ so that both $\cl(D)$ and $\cl(\ell^2D)$ are cyclic groups generated by prime forms of norm $\ell_0=3$ (so we can use $\ell_0$-volcanoes of depth 0; see part (d) of Problem 1).  This idealized setup is not always achievable, but it will work for our example using $\ell=17$ and $D=-2339$, with class number $h(D)=19$.

The key challenge is to map our set of $\ell$-volcanoes without using the polynomial $\Phi_\ell$.
Mapping the surface is easy: the vertices on the surface of our set of $\ell$-volcanoes are the roots of the Hilbert class polynomial $H_D$ (each root constitutes the surface of its own volcano).
The vertices on the floor are the roots of the Hilbert class polynomial $H_{\ell^2D}$, but this polynomial is much larger than $H_D$ and we don't want to compute it, since it would take time $\softO(\ell^4)$.
Instead we will use V\'{e}lu's formulas from Lecture 6 to compute a descending isogeny from each vertex on the surface.
The kernel of this isogeny is a cyclic subgroup of $E[\ell]$, and V\'{e}lu's formulas require us to enumerate the points in the kernel, which may lie in an extension field of degree as large as $\ell^2-1$ (the degree of the $\ell$-division polynomial).
But we will choose primes $p\equiv 1\bmod \ell$ that satisfy the norm equation $4p=t^2-\ell^2D$.  This ensures that the elliptic curves $E/\Fp$ with endomorphism ring $\O_K$ have rational $\ell$-torsion (provided we choose the correct twist); in this situation V\'{e}lu's formulas are very efficient.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{1}
\item With $\ell=17$ and $D=-2339$, find a prime $p\equiv 1\bmod \ell$ that satisfies $4p=t^2-\ell^2D$.  Note that this requires $t\equiv \pm 2\bmod \ell$, and with $t\equiv 2\bmod \ell$ we will have $p+1-t$ divisible by $\ell^2$.
Use Sage to compute the Hilbert class polynomial $H_D(X)$ and find the roots of $H_D\bmod p$.
For each of the roots $j_1,\ldots, j_h$ of $H_D$, construct an elliptic curve $E_i$ with $j$-invariant $j_i$, and attempt to find a point $P_i\in E(\Fp)$ with order $\ell$ by computing random $P_i=mP$ with $m=(p+1-t)/\ell^2$.  If you find $P_i\ne 0$ and $\ell P_i\ne 0$ then you will need to replace $E_i$ with a quadratic twist $y^2=x^3+d^2A+d^3B$, where~$d$ a not a square in $\Fp$
\end{enumerate}

We are now ready to apply V\'{e}lu's formulas to each pair $(E_i,P_i)$ to obtain an $\ell$-isogenous curve $E_i'$.
Since every curve $E_i'$ that is $\ell$-isogenous to $E_i$ lies on the floor, it does not matter which $P_i$ we choose, any point of order $\ell$ will work.
Below is a simplified algorithm that implements V\'{e}lu's formulas for the case where we have a cyclic subgroup generated by a point $P$ of odd order on an elliptic curve given in short Weierstrass form $y^2=x^3+Ax+B$ over a finite field $\Fp$ with $p>3$.

\begin{enumerate}
\setlength{\itemsep}{0pt}
\item
Set $t\leftarrow 0$, $w\leftarrow 0$, and $Q\leftarrow P$.
\item
Repeat $(l-1)/2$ times:
\begin{enumerate}[a.]
\item
Set $s\leftarrow 6Q_x^2+2A$, and then set $u\leftarrow 4Q_y^2 + sQ_x$.
\item
Set $t\leftarrow t + s$, $w\leftarrow w + u$, and $Q\leftarrow Q + P$.
\end{enumerate}
\item
Set $A'=A-5t$ and $B'=B-7w$.
\item
Output the curve $E'/\Fp$ defined by $y^2=x^3+A'x+B'$.
\end{enumerate}

In the description above $Q_x$ and $Q_y$ are the affine coordinates $(x.y)$ of the point $Q$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{2}
\item Implement the above algorithm and use it to compute elliptic curves $E_i'$ that are $\ell$-isogenous to the curves $E_i$ you computed in step 2.  Let $j_1',\ldots,j_h'$ be the corresponding $j$-invariants.
\end{enumerate}

Now comes the interesting part.  We want to enumerate the vertices on the floor of our our $\ell$-volcano, but there are no horizontal $\ell$-isogenies between vertices on the floor!  Instead, we must go up to the surface and back down, which amounts to computing an isogeny of degree $\ell^2$.  If we return to the same vertex this is just the multiplication-by-$\ell$ map (the composition of an $\ell$-isogeny with its dual), but otherwise it is a cyclic isogeny of degree $\ell^2$,
corresponding to the CM action of a proper $\O'$-ideal of norm $\ell^2$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{3}
\item For $(\frac{D}{\ell})=-1$, show that there are $\ell$ inequivalent integral primitive positive definite binary quadratic forms $(\ell^2,b,c)$ of discriminant $\ell^2D$ (in our example these will all be reduced forms).
These forms generate a cyclic subgroup $G$ of $\cl(\ell^2D)$ of order $\ell+1$.
For $\ell=17$ and $D=-2339$, determine a generator $f=(a,b,c)$ for $G$.
\end{enumerate}

We don't want to use $\Phi_{\ell^2}$ to compute the action of $f$ (we don't even know $\Phi_\ell$ yet!).
But as in problem 1 of Problem Set 11, we can compute the action of an $\O'$-ideal of large norm using the action $\O'$-ideals of much smaller norm.  In our example, we can use an $\O'$-ideal of norm $\ell_0=3$ to enumerate all the vertices on the floor of our set of volcanoes, and then determine the action of $f$ by computing a discrete logarithm in $\cl(\ell^2D)$.
Recall that we chose $D$ so that a prime form of norm 3 generates $\cl(\ell^2D)$, so this is easy.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{4}
\item Use $\Phi_{\ell_0} = \Phi_3$ to enumerate all the vertices on the floor as a cycle of 3-isogenies.
\item Compute the discrete logarithm $k$ of the form $f$ from part \textbf{(d)} with respect to a prime form of norm $\ell_0=3$ in $\cl(\ell^2 D)$.
There is no need to distinguish inverses, and you should find that $(\ell+1)k\equiv 0\bmod h(\ell^2D)$.
Feel free to use brute force (a linear search); the time will be dominated by later steps in any case.
Knowing $k$, you can now identify the subsets in the enumeration of part \textbf{(e)} that correspond to cosets of $G$.
Each of these subsets will contain exactly one the $j$-invariants $j_i'$ that you computed in step 3 and corresponds to the  $\ell+1$ ``children" of $j_i$ (its neighbors on the floor).
\item For each of $\ell+2$ vertices $j_i$ on the surface, compute the polynomial $\phi_i(Y)=\Phi_\ell(j_i,Y)=\prod_n (Y-j_{im})$, where the $j_{im}$ range over the $\ell+1$ children of $j_i$ that you identified in part~\textbf{(f)}.
Then, for $k$ ranging from $0$ to $\ell+1$,  interpolate the unique polynomial $\psi_k(X)$ of degree at most $\ell+1$ for which $\psi_k(j_i)$ is equal to the coefficient of $Y^k$ in $\phi_i(Y)$.  You can do this with Sage: first create the polynomial ring \texttt{R.<X>=PolynomialRing(GF(p))}, and then use
\begin{center}
\texttt{R.lagrange\_polynomial([(x0,y0),(x1,y1),\ldots,(xn,yn)])}
\end{center}
to compute the unique polynomial $f(X)$ of degree at most $n$ for which $f(x_i)=y_i$.   Note that $\psi_{\ell+1}(X)$ must be the constant polynomial 1.

Finally, compute $\Phi_\ell(X,Y)=\sum_{k=0}^{\ell+1}\psi_k(X)Y^k\bmod p$.
As a sanity check, verify that the coefficients are symmetric: $\Phi_\ell(X,Y)=\Phi_\ell(Y,X)$.
\end{enumerate}
If you need to debug your algorithm, you may find it helpful to compute the Hilbert class polynomial $H_{\ell^2D}(X)$  and then verify that the $j$-invariants~$j_i'$ computed in step 3 are actually roots of $H_{\ell^2D}\bmod p$.


Provided that $D = O(\ell^2)$ and $\ell_0=O(\log\ell)$, one can show that the algorithm you have implemented takes time $O(\ell^2\log^3p\log\log p)$, which is nearly optimal, since it is quasi-linear in the size of $\Phi_\ell\bmod p$.  By applying the same algorithm to a sufficiently large set of suitable primes $p_i$ (it suffices to have $\sum \log p_i > 6\ell\log\ell + 18\ell$), one can then use the Chinese remainder theorem (as in problem 2 of Problem Set 11) to compute the coefficients of $\Phi_\ell\in\Z[X,Y]$.  Under the GRH, the total time to compute $\Phi_\ell$ over $\Z$ is $O(\ell^3\log^3\ell\log\log\ell)$; see \cite{BLS}.  In practical terms, this algorithm can be used to compute $\Phi_\ell$ even when $\ell$ is well into the thousands and $\Phi_\ell$ is hundreds of gigabytes.
\bigskip

To convince ourselves that $\Phi_{17}\bmod p$ is correct, let's use it to compute a 17-volcano.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{7}
\item
Using the same prime $p$, pick a different discriminant $D$ for which $4p=t^2-v^2D$, with $17\nmid v$ and $(\frac{D}{17})=1$, such that $h(D)\ge 10$.
Use Sage to find a root $j_0\in\Fp$ of the Hilbert class polynomial $H_{D}(X)\bmod p$.
Then use the polynomial $\Phi_{17}(X,Y)\bmod p$ to enumerate the vertices in the 17-volcano containing $j_0$, which has depth~0 and degree 2 (since $\ell\nmid v$ and $\left(\frac{D}{17}\right)=1$) and therefore consists of a single cycle.  List the $j$-invariants of this cycle in order.
\item Let $\a$ be a prime ideal of norm $17$ in the order $\O$ of discriminant $D$.  Compute the order of $[\a]$ in $\cl(\O)$ and verify that it matches the length of the cycles you computed in part (h).  You can construct the the order $\O$ in Sage via \texttt{O=QuadraticField(D).maximal\_order()}) to create the order $\O$, then use \texttt{a=O.ideal(17).factor()[0][0]}) to construct $\a$; you want to determine the list $n\ge 1$ such that $\a^n$ is principal.
\end{enumerate}


\subsection*{Problem 3. Supersingular isogeny graphs (50 points)}

Let $p$ be and $\ell$ be distinct primes.
Recall from Theorem 14.16 that the $j$-invariant of every supersingular elliptic curve over $\Fpbar$ lies in $\Fptwo$.
In this problem you will explore some properties of the supersingular components of $G_\ell(\Fptwo)$.\footnote{There is in fact only one supersingular component of $G_\ell(\Fptwo)$, see \cite[Cor.\,78]{kohel}, but won't use this.}

\begin{enumerate}[{\bf(a)}]
\item Compute the graph of the component of $G_2(\F_{97^2})$ containing the supersingular $j$-invariant $1$.
You may wish to draw the graph on paper, but in your write-up just give a complete list of directed edges.

\item Prove that every supersingular vertex in $G_\ell(\Fptwo)$ has out-degree $\ell+1$, and conclude that no supersingular component of $G_\ell(\Fptwo)$ is an $\ell$-volcano.
Show by example that the in-degree need not be $\ell+1$.

\item Design an efficient \emph{Las Vegas} algorithm that, given an arbitrary $j$-invariant in $\Fptwo$, determines whether it lies in an ordinary or supersingular component of $G_\ell(\Fptwo)$ by detecting the difference between these components as abstract graphs.  Prove that if $\ell=O(1)$ then the expected running time of your algorithm is $\tilde{O}(n^3)$, where $n=\log p$.\footnote{As usual, the soft $\tilde{O}$-notation ignores factors that are polylogarithmic in $n$.}
\end{enumerate}

The fastest known algorithms for computing the trace of Frobenius all have complexity $\Omega(n^4)$, so your algorithm provides a way to determine whether a given elliptic curve over a finite field is ordinary or supersingular that is asymptotically more efficient than checking whether the trace of Frobenius is divisible by $p$, and in practice, it should be \emph{much} faster.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{3}
\item By applying your algorithm to $G_2(\Fptwo)$, determine which of the following $j$-invariants is supersingular.
List the running time of your algorithm in each case.
\begin{enumerate}[{\bf (i)}]
\item $p=2^{64}+81$:
\begin{lstlisting}
p=2^64+81
R.<t> = PolynomialRing(GF(p))
F.<a> = GF(p^2, modulus=t^2+5)
j1=8326557536028784306*a + 13186271742734526835
j2=17095442389470987916*a + 5391379569813173462
j3=8201451720284342414*a + 1239990603471114829
j4=3832397532494683106*a + 3456346199771023610
j5=6995663267023152807*a + 5118305496003400382
\end{lstlisting}
\item $p=2^{498}(2^{17}-1)+5^2\cdot11^2$:
\begin{lstlisting}
p=2^498*(2^17-1)+5^2*11^2
F.<a>=GF(p^2)
j1=F(1068730309040382537178579357918315740437237673601\
46365282990696994391226239701748935923381766723513633\
617314116677847252974815762274295992015602852450016138)
j2=F(9307837638889485802864130889597342112431240717617\
79743203146570670576874073881819468942290046762690325\
81122360838583736151525289450839654218958090187901480)
\end{lstlisting}
\end{enumerate}
Be patient, it may take a while for your program to run on the last two examples (but it should not take more than an hour).
\end{enumerate}


\subsection*{Problem 4. Pairing attack on the discrete logarithm problem (50 points)}
In the early days of elliptic curve cryptography supersingular curves were initially considered ideal candidates for discrete logarithm based cryptography (using a prime order subgroup of the rational points) because for these curves it is easy to determine the group order ($p+1$ over prime fields for $p>3$) and there are special techniques to speed up scalar multiplication.
However, supersingular curves were quickly ruled out once it was discovered by Menezes, Okamato, and Vanstone \cite{MOV} that one can use the Weil pairing to reduce the computation of a discrete logarithm in an order $n$ subgroup of $E(\Fq)$ to the computation of a discrete logarithm in a finite field $\F_{q^k}$ that contains the group $\mu_n\subseteq \Fqbar$ of $n$th roots of unity.
As we saw in Lecture 11, there are subexponential-time algorithms to solve the discrete logarithm problem in a finite field, whereas no such algorithm is known for the discrete logarithm problem on an elliptic curve.
In general $k$ will be very large (exponential in $\log q$) and this reduction does not make the problem of computing discrete logarithms in $E(\Fq)$ any easier.  But for supersingular curves this is not the case.

Let $p>3$ be a prime, let $E/\Fp$ be a supersingular curve, let $n>2$ be a divisor of $p+1$, and let $\mu_n$ denote the multiplicative group of $n$th roots of unity in $\Fpbar$.

\begin{enumerate}[{\bf(a)}]
\item Prove that $\mu_n\not\in \Fp^\times$ and $E[n]\not\subseteq E(\Fp)$, but $\mu_n\subseteq \Fptwo^\times$ and $E[n]\subseteq E(\Fptwo)$.
\end{enumerate}

Let $P\in E(\Fp)$ be a point of order $n$, and let $Q\in \langle P\rangle$.
Consider the following algorithm Las Vegas algorithm to compute $\log_P Q$:
\begin{enumerate}
\setlength{\itemsep}{0pt}
\item Generate a random point $R\in E(\F_{p^2})$ and compute $S=mR$, where $m=(p+1)/n$.
\item Compute $a=e_n(S,P)$, and if $a=1$ then return to step 1.
\item Compute $b=e_n(S,Q)$.
\item Compute $\log_a b$ in $\F_{p^2}^\times$ and output the result.
\end{enumerate}

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{1}
\item Prove that the expected number of times the algorithm executes step 1 is $1+o(1)$.
\item Prove that the algorithm outputs $\log_P Q$.
\end{enumerate}

The expected running time the algorithm is completely dominated by the time to compute $\log_a b $ in $\Fptwo^\times$, which is heuristically $L[1/3,c]$.
\medskip

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{3}
\item Let $E$ be an elliptic curve defined over a number field $L$ with CM by a maximal order in an imaginary quadratic field of discriminant $K$  and let $\p$ be a prime ideal of $\O_L$ with prime norm $p$ such that $E$ has good reduction at $\p$.  Prove that if $\left(\frac{D}{p}\right)=-1$ then the reduction of $E$ modulo $\p$ is a supersingular elliptic curve over $\Fp$.
\end{enumerate}

\noindent
Let $n=10^{14}+2367$ (which is prime) and let $p=2n-1$ (also prime).

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{4}
\item Construct an elliptic curve $E/\Fp$ such that $E[n]\subseteq E(\Fptwo)$.
\end{enumerate}

Representing $\Fp$ by integers in $[0,p-1]$, choose $P_0\in E(\Fp)$ so that $x(P_0)$ is the least integer greater than your student ID and $y(P_0)$ is minimal, and let $P=2P_0$.
In the unlikely event that $P=0$, increment your student ID and repeat until $P\ne 0$.
Then choose $Q_0\in E(\Fp)$ so that $x(Q_0)$ is the least integer greater than twice your student ID and $y(Q_0)$ is minimal, and let $Q=2Q_0$.
Then both $P$ and $Q$ lie in $E[n]$ and you can use the above algorithm to compute $\log_P Q$, with $m=2$.
Here are a few tips to help you:

\begin{itemize}
\item To create the field $\F_{p^2}$ in Sage use \texttt{F2 = GF(p**2)}.
\item To generate $R$ use \texttt{E.change\_ring(F2).random\_element()}.
\item To compute $e_n(S,P)$ use \texttt{S.weil\_pairing(P.change\_ring(F2),N)}.
\item To compute $\log_a b$ use \texttt{b.log(a)}.
\end{itemize}

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{5}
\item Compute $\log_P Q$.  In your answer list the points $P_0,P,Q_0,Q$, the values of $a$ and~$b$, the integer $n=\log_a b$, and the running time of your algorithm (which should be well under a minute).
Be sure to check your answer by verifying that $nP=Q$.
\end{enumerate}

\begin{remark}
You should not be particularly impressed by this running time, since you can easily beat it with a careful implementation of the baby-steps giant-steps or Pollard rho algorithms.
But for larger values of $p$ and $N$ this algorithm will easily outperform any generic method.
Unfortunately Sage does not have a particularly fast implementation for discrete logarithms in non-prime finite fields, so I intentionally chose a small example.
\end{remark}

\subsection*{Problem 5. A fast Las Vegas algorithm to compute ${E(\Fp)}$ (50 points)}

Problem 2 of Problem Set 5 gave a Las Vegas algorithm to compute the structure of the group $E(\Fp)\simeq \Z/m\Z\oplus\Z/n\Z$, but its running time was $\exp(\frac{1}{4}\log p+o(1))$, exponential in $\log p$.
In this problem, following Miller \cite{miller}, you will develop a much faster algorithm to compute $E(\Fp)$.
Strictly speaking it is not polynomial-time because it requires the factoring the integer $d=\gcd(\#E(\Fp),p-1)$, but typically $d$ will either be small (in which case the problem is easy), or it will have only one large prime factor $\ell$, in which case factoring $d$ is easy but computing the structure of $E(\Fp)$ with the algorithm from Problem Set 5 will be very difficult if $\ell^2$ divides $\#E(\Fp)$.
In any case, this does give a subexponential-time Las Vegas algorithm, since we can always factor $d$ in subexponential time using a Las Vegas algorithm (the best proven bound is $L[1/2,c]$, but heuristically this can be done in time $L[1/3,c]$).

\begin{enumerate}[{\bf(a)}]
\item Let $\ell$ be a prime.  Prove that if $E[\ell]\subseteq E(\Fp)$ then $\ell|(p-1)$ and $\ell^2|\#E(\Fp)$.
\end{enumerate}

Let $N=\#E(\Fp)$ and write $N$ as $N=N_0N_1$, where $N_0$ and $N_1$ are relatively prime and $N_1$ is divisible only by primes $\ell$ that divide $p-1$ and whose square divides $N$.
By part \textbf{(a)}, when computing the structure of $E(\Fp)$, we can restrict our attention to $E(\Fp)[N_1]$.
Consider the following algorithm to compute the structure of $E(\Fp)$, which takes as input the elliptic curve $E/\Fp$, the integers $N_0$ and $N_1$, and the prime factorizations of $N_1$.

\begin{enumerate}
\setlength{\itemsep}{0pt}
\item Generate random points $P_0,Q_0\in E(\Fp)$ and put $P:=N_0P_0$ and $Q:=N_0Q_0$.
\item Using the prime factorization of $N_1$, compute $s:=|P|$ and $t:=|Q|$.
\item Let $r=\lcm(s,t)$ and compute $\zeta:=e_r(P,Q)$.
\item Using the prime factorization of $N_1$, compute $n:=|\zeta|$.
\item If $rn = N_1$ then put $m=rN_0$ and output $\Z/m\Z\oplus\Z/n\Z$, otherwise go to step 1.
\end{enumerate}

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{1}
\item Prove that when the algorithm terminates we have $E(\Fp)\simeq \Z/m\Z\oplus \Z/n\Z$.
\item Prove that in step 3 we have $\zeta\in\Fp^\times$.
\item Prove that the expected number of times the algorithm repeats step 1 is  $O(\log \log p)$.
You may use Mertens' bound $\sum_{\ell\le x} \frac{1}{\ell} =\log\log x+O(1)$, where $\ell$ ranges over primes.\footnote{One can modify the algorithm so that the expected number of repeats is actually $O(1)$.}
\item Let $g\in G$ be an element of a generic group with exponent $\lambda$ (so $\lambda g =0$).
Prove that, given the prime factorization of $\lambda$ you can compute the order of $g$ using $(\log\lambda)^{1+o(1)}$ group operations.
(You may wish to review Lecture 10 on generic algorithms).
\item Prove that the running time of the algorithm above is $(\log p)^{2+o(1)}$.
\end{enumerate}

\begin{remark}
As noted above, this only gives a subexponential-time algorithm to compute $E(\Fp)$ if we are not given the factorization of $N_1$.
But it is known that we can do this in \emph{average polynomial time} \cite{FPS}, in the following sense: for any prime $p$, if we pick a random $A,B\in \Fp$ the expected time to compute $E(\Fp)\simeq \Z/m\Z\oplus\Z/n\Z$ for the curve $E\colon y^2=x^2+Ax+B$ is polynomial in $\log p$.
\end{remark}

\subsection*{Problem 6. The Birch and Swinnerton-Dyer Conjecture (50 points)}

The goal for this problem is to lead you to a formulation of the (weak) Birch and Swinnerton-Dyer conjecture.
The main difficulty here is not for you to prove a precisely stated question, but rather for you to formulate a precise question, starting from some data and some general suggestions.
This means that parts of the problem are deliberately vague; making the questions more precise is part of the problem.
Other than part~\textbf{(a)}, you are not expected to prove anything; heuristic arguments are fine.

One of the outstanding \href{http://www.claymath.org/millennium-problems/millennium-prize-problems}{Millennium Prize Problems} is the famous conjecture of Birch and Swinnerton-Dyer, which concerns the ranks of elliptic curves over $\Q$.  Recall from Lecture 1 that the Mordell-Weil theorem implies
\[E(\Q) = E(\Q)_{\text{tors}} \oplus \Z^r. \]
As opposed to the torsion subgroup, the rank $r$ of the Mordell-Weil group $E(\Q)$ is far less understood; we do not have a fully general algorithm to compute $r$, and mathematicians do not even agree on whether $r$ should be bounded or not (so not only can't we prove a conjecture, we don't even know what the right conjecture is!).  However, in the 1960s, Birch and Swinnerton-Dyer carried out computations on the EDSAC computer at Cambridge University that led them to conjecture a deep relationship between the $L$-series of $E$ and the rank $r$ of the Mordell-Weil group.
In this problem you will develop a conjecture and investigate the evidence for it.

Recall from Lecture 25 that the $L$-series of $E/\Q$ is defined by
\[L_E(s) = \prod_p L_p(p^{-s})^{-1} = \prod_p (1 -a_p p^{-s} + \chi(p)p^{-2s+1})^{-1}, \]
where the Dirichlet character $\chi(p) = 0$ if $E$ has bad reduction at $p$ and $1$ otherwise.\footnote{Recall that this assumes a minimal Weierstrass model for $E$.}  This converges for $\Re(s) >3/2$; however by the modularity theorem, it admits an analytic continuation to the entire complex plane.

\begin{enumerate}[{\bf(a)}]

\item Assume that $E$ is given in affine coordinates by the equation $y^2 = x^3 + Ax + B$ with $A, B \in \Z$.\footnote{This need not be a minimal Weierstrass model, but you may assume it is if you wish.}  A rational point $(x_0:y_0:z_0)\in E(\Q)$ gives a solution to
\[y^2z \equiv x^3 + Axz^2 +Bz^3 \pmod{p^n}, \]
and hence a point on $E$ modulo $p^n$ for all $p\nmid \Delta(E)$ and $n\ge 1$.  Let $N_{p^n}$ denote the number of projective solutions $(x_0:y_0:z_0)$ to this congruence (over $\Z/p^n\Z$).  Using Hensel's lemma (see problem~5 of Problem Set~2) prove that 
\[N_{p^n} = p^{n-1}N_p \]
for all $p \nmid \Delta(E)$.  Conclude that
\[ \lim_{n \to \infty} \frac{N_{p^n}}{p^{n}} = \frac{N_p}{p},\]
except for finitely many $p$.  This quantity $\lim_{n \to \infty} \frac{N_{p^n}}{p^{n}}$ represents the density of $p$-adic points on $E$.  Give a plausible relation with $r$.  

\item Let $S$ be the set of primes of bad reduction of $E$.  Define
\[f_E(X) = \prod_{\substack{p \not\in S\\p \leq X}} \frac{N_p}{p}, \]
What is the relationship between $f_E(X)$ and $L_E(s)$?

\item Consider the elliptic curve\footnote{In 1938, this was the highest rank known, due to Billings.} $E$ with rank $3$ given by
\[ y^2 = x^3 - 82x.\]
Compute and plot the values of 
\[f_E(X) = \prod_{\substack{p \not\in S \\ p\leq X}} \frac{N_p}{p} \]
for $X$ up to at least $10^6$ (or further if you like).  You can use the Sage method \texttt{E.aplist} to efficiently compute a list of $a_p$ values at all primes $p\le X$ (including primes of bad reduction).  For primes of good reduction $a_p$ is the trace of Frobenius of $E\bmod p$, from which you can derive $N_p$.
What appears to be the asymptotic growth of the function $f_E(X)$?
Make a plot of your results with an appropriate choice of scale on the coordinate axes so your answer is apparent.
Attach relevant plots in your solutions.

\item Repeat part \textbf{(c)} for the following curves of the form
\[E_i : y^2 = x^3 - d_i^2 x,\]
for the values:
\begin{center}
\begin{tabular}{c | c | c}
 & $d_i$ & rank \\ \hline \hline
$E_1$ & 1 & 0 \\
$E_2$ & 5 & 1\\
$E_3$ & 34 & 2\\
$E_4$ & 1254 & 3 \\
$E_5$ & 29274 & 4\\
\end{tabular}
\end{center}
Display your final plots (with the appropriate scaling of the axes) together.

\item Combining your results from parts \textbf{(b)}, \textbf{(c)}, and \textbf{(d)} above, make a precise conjecture on the relationship between $L_E(s)$ and the rank of $E$. Your conjecture should be precise enough that different ranks give rise to different behaviors of the $L$-function. (Hint: You might need to do more work in \textbf{(b)} in order to give a more precise relationship -- there is a natural interplay between conjecture and computation.)

\item Choose $5$ random elliptic curves with $|A|, |B| < 100$ and conjecturally assign their ranks.  Note: you can use Sage to check your answer, but you must provide evidence based upon your work in previous parts to receive full credit.\footnote{While we do not have a general algorithm to compute the rank of $E/\Q$, for small $|A|$ and $|B|$, Sage can easily do so.}

\end{enumerate}

\subsection*{Problem 7. Classifying subgroups of $\GL_2(\F_\ell)$ (50 points)}

Let $E$ be an elliptic curve defined over $\Q$.
Recall that for each integer $n>1$, the $n$-torsion of $E(\Qbar)$ is a rank $2$ $(\Z/n \Z)$-module we denote by $E[n]$.
As explained in Problem Sets 3 and 6, the action of the absolute Galois group $G_\Q := \Gal(\Qbar/\Q)$ on the coordinates of points gives rise to an action on the set $E(\Qbar)$ that commutes with the group law.
Hence the action of $G_\Q$ preserves $E[n]$ and gives rise to a linear representation of the absolute Galois group
\[
\rho_{E,n} \colon G_\Q \to \Aut(E[n]) \simeq \GL_2(\Z/n\Z),
\]
which we call the \emph{mod-$n$ Galois representation} attached to $E$.
In this problem an the next we are concerned only with the case that $n  = \ell$ is prime.

In this case, a foundational result in the subject of Galois representations of elliptic curves is the following theorem of Serre:
%\footnote{This theorem is the ``hard step" in proving Serre's open image theorem, which states that for any elliptic curve over a number field without CM, the image of the adelic Galois representation $G_K \to \varprojlim_n \Aut(E[n]) = \prod_\ell \GL_2(\Z_\ell)$ is open, in particular of finite index.  The proof of such a theorem breaks into two parts.  The first (easier) part is to prove that for a fixed $\ell$, the image of the $\ell$-adic representation is open in $\GL_2(\Z_\ell)$.  But this does not suffice, because if there existed infinitely many primes for which the $\ell$-adic representation was not surjective (e.g. of index greater than 1), then the image of the adelic representation would not be of finite index in $\prod_\ell \GL_2(\Z_\ell)$.  Hence the second (hard) part is to prove that the $\ell$-adic representation is surjective for $\ell$ sufficiently large.  This reduces to the Theorem quoted here (in the case $K = \Q$) that the mod-$\ell$ representation is surjective for $\ell$ sufficiently large.}

\begin{theorem}[Serre, 1972]
Let $E$ be an elliptic curve over $\Q$ which does not have CM.  Then for all but finitely many primes $\ell$, the image of the mod-$\ell$ Galois representation is surjective:
\[\rho_{E, \ell}(G_\Q) = \GL_2(\F_\ell). \]
\end{theorem}

\begin{remark}
It is conjectured that for all $E/\Q$ without CM we have $\rho_{E, \ell}=\GL_2(\F_\ell)$ for all $\ell > 37$.
There has been some recent progress in proving this, but it remains a major open problem.
\end{remark}

A key component of the proof of this theorem is understanding the maximal subgroups of $\GL_2(\F_\ell)$
In order to discuss subgroups of $\GL_2(\F_\ell)$ in a basis-free manner, it is often convenient to write $\GL(V)$ where $V$ is a $2$-dimensional vector space over $\F_\ell$ and $\GL(V)$ denotes its group of automorphisms.
In this problem you will give a complete classification of the maximal subgroups of $\GL_2(V)$.


Let $L_1$ and $L_2$ be distinct $1$-dimensional subspaces of $V$, which we can think of as lines through the origin in $V$, and let $C_s$ be the subgroup of $\GL(V)$ that preserves both $L_1$ and $L_2$ (individually, no swapping allowed).

\begin{enumerate}[{\bf(a)}]

\item Show that for $\ell \neq 2$, the subgroup $C_s$ uniquely determines the lines $L_1, L_2 \subset	 V$ (and hence is equivalent to specifying two such lines).

\end{enumerate}

We call such a $C$ a \emph{split Cartan subgroup} of $\GL(V)$.  If we choose a basis for $V$ compatible with the decomposition $V = L_1 \oplus L_2$, we then have
\[
C_s = \begin{pmatrix} \ast & 0 \\ 0 & \ast \end{pmatrix},
\]
where $\ast$ indicates any element of $\F_\ell^\times$.  From this we see that $C \simeq \big(\F_\ell^\times \big)^2$ is an abelian group of order $(\ell-1)^2$.

As an $\F_\ell$-vector space, $\F_{\ell^2} \simeq \F_\ell^2$; but $\F_{\ell^2}$ also has a multiplicative structure, and so the action of the multiplicative group $\F_{\ell^2}^\times$ on $\F_{\ell^2} \simeq V$ gives a cyclic subgroup $C_{ns}$ of $\GL(V)$ isomorphic to $\F_{\ell^2}^\times$.  Such a subgroup $C_{ns}$ is called a \emph{non-split Cartan subgroup}.
We collectively refer to split and non-split Cartan subgroups as Cartan subgroups.
 
\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{1}
 
\item Show that for $\ell \neq 2$, if we fix a quadratic non-residue $\epsilon \in \F_\ell^\times$, then in an appropriate basis we have
\[
C_{ns} = \left\{ \begin{pmatrix} x &  \epsilon y \\ y & x \end{pmatrix} : x, y \in \F_\ell, (x,y) \neq (0,0) \right\}.
\]

\item Show that the intersection of any two distinct Cartan subgroups (either split or non-split) is the group of scalar matrices $Z=\left(\begin{smallmatrix}z&0\\0&z\end{smallmatrix}\right)$ with $z\in\F_\ell^\times$.

\item Show that any element $s \in \GL(V)$ with $\Delta(s) = \tr(s)^2 - 4 \cdot \det(s) \neq 0$ is contained in a unique Cartan subgroup, and determine a condition involving $\Delta(s)$ that specifies the type of Cartan.  Deduce that the union of all Cartan subgroups of $\GL(V)$ is the set of elements of order prime to $\ell$.  (If you are stuck, look at part {\bf{(h)}} below.)

\item Let $N$ denote the normalizer of a Cartan subgroup $C$ in $\GL(V)$, that is all elements $s \in \GL(V)$ such that $s C s^{-1} = C$.  Show that $(N : C) = 2$ and give an explicit description of this group in the split and non-split cases separately.

\end{enumerate}

It is easy to show that the group $Z$ of scalar matrices forms the center of $\GL(V)$.
We define $\PGL(V)$ to be the quotient of $\GL(V)$ by its center, so $\PGL(V) := \GL(V)/Z$.
Let $\varphi \colon \GL(V) \to \PGL(V)$ denote the quotient map.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{5}
\item Show that if $C$ is a split (resp. non-split) Cartan subgroup, then $\varphi(C) \subset \PGL(V)$ is cyclic of order $\ell-1$ (resp. $\ell +1$).    Show that the image in $\PGL(V)$ of a normalizer of a Cartan subgroup is a dihedral group.\footnote{For this problem, the product of two cyclic groups of order 2 (the Klein group) is a dihedral group.}
\end{enumerate}

By part {\bf{(d)}} above, it remains to understand the elements of $\GL(V)$ of order divisible by $\ell$.
A Borel subgroup $B$ of $\GL(V)$ is the group of automorphisms of $V$ fixing a specified line (through the origin).
A Borel subgroup of $\GL(V)$ has order $\ell (\ell-1)^2$.  After choosing an appropriate basis, this has the form
\[
B = \begin{pmatrix} \ast & \ast \\ 0 & \ast \end{pmatrix}.
\]
 
\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{6}
 \item Show that any element $s \in \GL(V)$ of order $\ell$ is conjugate to the matrix $\left(\begin{smallmatrix} 1 & 1 \\ 0 & 1\end{smallmatrix}\right)$.
 
 \item Using the fact that $\SL(V)$ is generated $\left(\begin{smallmatrix} 1 & 1\\ 0& 1\end{smallmatrix}\right)$ and $\left(\begin{smallmatrix} 1 & 0\\ 1 & 1\end{smallmatrix}\right)$, deduce that any subgroup of $\GL(V)$ of order divisible by $\ell$  either lies in a Borel subgroup, or contains $\SL(V)$.
 
\end{enumerate}

Let $k$ be any field.  If $H$ is a finite subgroup of $\PGL_2(k)$ of order prime to the characteristic of $k$ that is not cyclic or dihedral, then $H$ is isomorphic to either $A_4, S_4, $ or $A_5$.  (In the case $k = \C$, this result is well known and these subgroups correspond to the symmetry groups of the regular polyhedra: tetrahedron, cube/octahedron, and icosahedron/dodecahedron, respectively.)

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{8}
\item Using the above result, prove the classification theorem below.
\end{enumerate}

\begin{theorem}[Maximal subgroups of $\GL_2(\F_\ell)$]
Let $G$ be a subgroup of $\GL_2(\F_\ell)$; let $H$ denote the image of $G$ in $\PGL_2(\F_\ell)$.  Then one of the following holds:
\begin{enumerate}
\setlength{\itemsep}{0pt}
\item $G$ has order prime to $\ell$ and either:
\begin{enumerate}[(i)]
\setlength{\itemsep}{0pt}
\item $H$ is cyclic and $G$ is contained in a Cartan subgroup of $\GL_2(\F_\ell)$;
\item $H$ is dihedral and $G$ is contained in the normalizer of a Cartan subgroup $C$ of $\GL_2(\F_\ell)$ but not in $C$;
\item $H$ is isomorphic to $A_4, S_4$ or $A_5$ and we call $G$ exceptional;
\end{enumerate}
\item $G$ has order divisible by $\ell$ and either:
\begin{enumerate}
\setlength{\itemsep}{0pt}
\item[(iv)] $G$ is contained in a Borel subgroup;
\item[(v)] $G$ contains $\SL_2(\F_\ell)$.
\end{enumerate}
\end{enumerate}
\end{theorem}
\smallskip

\subsection*{Problem 8. Surjectivity of Mod-$\ell$ Galois Representations (50 points)}

This is a continuation of Problem 7, but you don't need to solve Problem 7 in order to do this problem, you can assume the classification theorem and any other results stated or proved in Problem 8.
Let $\ell$ be an odd prime and let $V$ be a 2-dimensional $\F_\ell$-vector space, with automorphism group $\GL(V)$, as in the previous problem, and let $\varphi\colon \GL(V)\twoheadrightarrow\PGL(V)$ denote the quotient map.

\begin{enumerate}[{\bf(a)}]
\item Let $s$ be an element of $\GL(V)$ whose order is not divisible by $\ell$, let $u=\tr(s)^2/\det(s)$, and let $r$ be the order of $\varphi(s)$ in $\PGL(V)$.
Prove that $u = \zeta_r + \zeta_r^{-1} + 2$, for some primitive $r$th root of unity $\zeta_r\in\F_{\ell^2}^\times$.
\item Suppose that we are in case (iii) of the classification theorem, in which $G$ is a subgroup of $\GL(V)$ whose image in $\PGL(V)$ is isomorphic to $A_4, S_4$, or $A_5$.
Prove that for all elements $s \in G$, $u = \tr(s)^2/\det(s)$ is equal to $4, 0, 1, 2$ or satisfies $u^2 - 3u+1 = 0$.  
\end{enumerate}

Now we are ready to use this classification to deduce some results about surjectivity of the mod-$\ell$ Galois representation
\[
\rho_{E,n} \colon G_\Q \to \Aut(E[n]) \simeq \GL(V),
\]
of an elliptic curve $E/\Q$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{2}

\item Let $G = \rho_{E, \ell}(G_\Q)$.  Using the Weil pairing, prove that the determinant map $G \to \F_\ell^\times$ is surjective.  Show that the image $H$ of the $G$ in $\PGL(V)$ contains a (normal) subgroup of index $2$.
Deduce that if $G \neq \GL_2(\F_\ell)$ then one of the following is true:
\begin{enumerate}[1.]
\setlength{\itemsep}{0pt}
\item $G$ is contained in the normalizer of a Cartan subgroup;
\item $G$ is contained in a Borel subgroup;
\item $G$ is exceptional and $H = S_4$.
\end{enumerate}
\end{enumerate}

\begin{remark}
As noted in Problem 7, it is a famous conjecture that for $\ell > 37$, the mod-$\ell$ Galois representation is surjective for $E/\Q$ without CM.  This has been proven in all of these cases except for $G$ contained in the normalizer of a non-split Cartan.
\end{remark}

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{3}
\item Prove that any element of the normalizer of a Cartan subgroup that does not lie in the Cartan subgroup itself has trace $0$.

\item Again let $G = \rho_{E, \ell}(G_\Q)$.  Determine three types of elements (specified by their trace and determinant) such that if $G$ contains these elements, then $G = \GL_2(\F_\ell)$.

\item Let $E$ be the elliptic curve 
\[
y^2 + y = x^3 - x^2,
\]
which has good reduction outside 11.
By considering the Frobenius elements $\pi_2 = \rho_{\ell, E}(\Frob_2)$ and $\pi_3 = \rho_{\ell, E}(\Frob_3)$, and using your criterion above, show that $\rho_{E, \ell}$ is surjective for all $\ell \geq 13$ satisfying $\kron{11}{\ell} = -1$.
\end{enumerate}

\subsection*{Problem 9. Survey}

Complete the following survey by rating each problem you attempted on a scale of 1 to~10 according to how interesting you found it (1 = ``mind-numbing," 10 = ``mind-blowing"), and how difficult you found it (1 = ``trivial," 10 = ``brutal").  Also estimate the amount of time you spent on each problem to the nearest half hour.

\begin{center}
\begin{tabular}{l|r|r|r|}
& Interest & Difficulty & Time Spent\\\hline
Problem 1 & & & \\\hline
Problem 2 & & & \\\hline
Problem 3 & & & \\\hline
Problem 4 & & & \\\hline
Problem 5 & & & \\\hline
Problem 6 & & & \\\hline
Problem 7 & & & \\\hline
Problem 8 & & & \\\hline
\end{tabular}
\end{center}
\noindent
Also, please rate each of the following lectures that you attended, according to the quality of the material (1=``useless", 10=``fascinating"), the quality of the presentation (1=``epic fail", 10=``perfection"), the pace (1=``way too slow", 10=``way too fast", 5=``just right") and the novelty of the material (1=``old hat", 10=``all new").

\begin{center}
\begin{tabular}{l|l|r|r|r|r|r}
Date & Lecture Topic & Material & Presentation & Pace & Novelty\\\hline
5/8 & Isogeny volcanoes & & & & \\\hline 
5/10 & The Weil paring & & & & \\\hline 
5/15 & Modular forms & & & & \\\hline 
\end{tabular}
\end{center}

\noindent
Finally, if you have any comments about the course as a whole, in particular, things that you think would improve it in the future, please let me know!

\begin{thebibliography}{9}
\bibitem{BLS} R. Br\"oker,  K. Lauter, and A.V. Sutherland, \href{http://www.ams.org/journals/mcom/2012-81-278/S0025-5718-2011-02508-1/}{\textit{Modular polynomials via isogeny volcanoes}}, Mathematics of Computation \textbf{81} (2012), 1201--1231.
\bibitem{FPS} J.B. Friedlander, C. Pomerance, I.E. Shparlinski, \href{http://www.austms.org.au/Publ/Bulletin/V72P2/pdf/722-5116-FrPoSh.pdf}{\textit{Finding the group structure of elliptic curves over finite fields}}, Bulletin of the Australian Mathematical Society \textbf{72} (2005), 251--263.
\bibitem{kohel} David Kohel, \href{http://echidna.maths.usyd.edu.au/kohel/pub/thesis.pdf}{\textit{Endomorphism rings of elliptic curves over finite fields}}, PhD thesis, University of California at Berkeley, 1996.
\bibitem{MOV} A.J. Menezes, T. Okamato, and S.A. Vanstone, \href{http://ieeexplore.ieee.org.libproxy.mit.edu/xpl/articleDetails.jsp?arnumber=259647}{\textit{Reducing elliptic curve logarithms to logarithms in a finite field}}, IEEE Transactions on Information Theory \textbf{39} (1993), 1639--1646.
\bibitem{miller} V.S. Miller, \href{http://link.springer.com/article/10.1007%2Fs00145-004-0315-8}{\textit{The Weil pairing and its efficient calculation}}, J. Cryptology \textbf{17} (2004), 235--261.\bibitem{washington} L. C. Washington, \href{http://www.crcnetbase.com/isbn/978-1-4200-7146-7}{\textit{Elliptic curves: Number theory and cryptography}}, second edition, CRC Press, 2008.
\end{thebibliography}

\end{document}