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

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

\subsection*{Description}

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

\noindent\textbf{Instructions}: Either solve \textbf{one} of Problems 1 and 2 or \textbf{both} or Problems 3 and 4.  Then complete Problem~5, which is a survey.
This \href{https://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783 Problem Set 12.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 as 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 an easier and faster algorithm using isogeny volcanoes.
The strategy is to use a CRT approach, with primes $p$ 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, 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 4 of problem 2).  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 (see \cite[\S 12.3]{washington}) 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$

As a sanity check, you may want to pick one of the $E_i$ and use Sage to verify that $E_i(\Fp)$ has $\ell$-rank 2, but this is not part of the algorithm.
\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}
\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}

Now we certainly 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 4 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 5 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~6.
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}f_k(X)Y^k\bmod p$.
\end{enumerate}

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

Now to convince ourselves that we have really computed $\Phi_{17}\bmod p$, let's use it to enumerate the roots of a completely \emph{different} Hilbert class polynomial.

\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 $v$ not divisible by 17 and $(\frac{D^*}{\ell})=1$, and such that $h(D^*)>4$.
Use Sage to compute all the roots of the Hilbert class polynomial $H_{D^*}(X)\bmod p$,  and then use the polynomial $\Phi_{17}(X,Y)\bmod p$ to organize the roots into cycles of 17-isogenies (there will may well be only one 17-cycle, this depends on the $D$ you pick).
\end{enumerate}

Note that $\Phi_{17}(X,Y)\bmod p$ must permute the roots of $H_{D^*}(X)\bmod p$, and this permutation must be a product of cycles, each with length equal to the order of the prime forms of norm 17 in $\cl(D^*)$ (since the roots of $H_{D^*}$ are a $\cl(D^*)$-torsor). 

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 1 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 many gigabytes.

\subsection*{Problem 3. Atkin-Morain ECPP (50 points)}
The bottleneck in the Goldwasser-Kilian elliptic curve primality proving algorithm is the time spent counting points on randomly generated elliptic curves in the hope of finding one with a suitable number of points (namely, the product of a large prime and a smooth co-factor).
Atkin and Morain proposed an alternative approach in \cite{AM} that uses the CM method to construct an elliptic curve that is guaranteed to have a suitable number of points.  This yields a much faster algorithm, with a heuristic running time of $\softO(n^4)$ that makes it the
method of choice for general purpose primality proving.  While its running time is not provably polynomial time, in practice it is faster than even randomized versions of the AKS algorithm that run in $\softO(n^4)$ expected time \cite{bernstein}.
\medskip

\noindent
Given a smoothness bound $B$ and probable prime $p$, the algorithm proceeds as follows:
\begin{enumerate}
\item Select a fundamental discriminant $D$ for which $4p=t^2-v^2D$ has a solution $(t,v)$ such that $m=p+1\pm t$ can be factored as $cq$, where $c>1$ is $B$-smooth and $q>(p^{1/4}+1)^2$ is a probable prime.\footnote{For $D=-3,-4$ there are other possible curve orders that can be used, but we will ignore them.}
\item Find a root $j$ of $H_D\bmod p$ and use it to construct an elliptic curve $E/\Fp$ in Weierstrass form $y^2=x^3+Ax+B$, where $A=3j(1728-j)$ and $B=2j(1728-j)^2$.  If unable to find a root of $H_D\bmod p$ within, say, twice the expected amount of time, perform a Miller-Rabin test on $p$.
If it fails then report that $p$ is not prime and otherwise repeat this step.
\item Generate a random $Q\in E(\Fp)$ with $P=cQ\ne 0$ and verify that $qP=0$.  If not, replace $E$ with a quadratic twist $\tilde{E}\colon y^2=x^3+d^2Ax+d^3B$, for some non-residue~$d$, and repeat this step.  If the verification $qP=0$ fails for $E$ and its twist, or if anything else goes wrong (e.g., a square-root computation or inversion fails), report that $p$ is not prime.
\item Output the certificate $(p,A,B,x,y,q)$, where $P=(x,y)$.
\end{enumerate}

As with the Goldwasser-Kilian algorithm, for $q > B$ one then proceeds to construct a primality certificate for $q$ using the same algorithm,  producing a chain of primality certificates that terminates with a prime $q\le B$ whose primality is verified by trial division (see Lecture~13).

As described above, the algorithm does not achieve a heuristic running time of $\softO(n^4)$.
The computation is (perhaps surprisingly) dominated by the cost of solving the norm equations in step 1, which is in turn dominated by the time spent computing square-roots of~$D$ modulo $p$ in Cornacchia's algorithm.
In order to achieve a heuristic time of $\softO(n^4)$ one selects a set of primes $S$ and restricts the discriminants $D$ to products of pairs of primes in $S$.  By computing square-roots modulo $p$ for all the primes in $S$, one can then efficiently compute the square-root modulo $p$ of any such $D$; see \cite{morain} for details.  For the purposes of this problem, you do not need to implement this optimization, it only becomes worthwhile when $p$ is very large.

\begin{enumerate}[{\bf (a)}]
\item Implement the Atkin-Morain ECPP algorithm described above in Sage and use it to construct a primality proof for the least prime greater than $2^{500}N$, where~$N$ is the last 4 digits of your student ID, using the smoothness bound $B=2^{20}$ (you may want to tweak this to optimize the time spent searching for candidate curve orders, a smaller~$B$ means less time spent trial-dividing candidate $m$'s but a lower probability of success)
You can use the \texttt{norm\_equation} function in the Sage worksheet linked to above to solve the norm equations in step 1.
In your implementation, create the finite field $\Fp$ in Sage using \texttt{GF(p,proof=false)} to prevent Sage from trying to prove that~$p$ is prime by itself.  You can use the \texttt{is\_pseudoprime} function in Sage to test whether~$q$ is a probable prime after using trial-division to remove the $B$-smooth factor $c$.  You needn't implement the Miller-Rabin test in step 2, as it is extremely unlikely to be necessary.

In your write-up, do not list all the primality certificates in full.
Just give a table that lists just the discriminant $D$ and the prime $q$ used for each certificate, as well as the time spent constructing each certificate.
\end{enumerate}


\subsection*{Problem 4. 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 several minutes for your program to run on the last two examples (but it should not take more than 10 or 20 minutes).
\end{enumerate}

\subsection*{Problem 5. 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
\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
4/30 & Main theorem of CM & & & & \\\hline 
5/4 & Isogeny volcanoes & & & & \\\hline 
\end{tabular}
\end{center}

\noindent
Please feel free to record any additional comments you have on the problem sets or lectures, in particular, ways in which they might be improved.

\begin{thebibliography}{9}
\bibitem{AM} A.O.L. Atkin and F. Morain, \href{http://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1199989-X/}{\textit{Elliptic curves and primality proving}}, Mathematics of Computation \textbf{61} (1993), 29--68.
\bibitem{bernstein} D.J. Bernstein, \href{http://www.ams.org/journals/mcom/2007-76-257/S0025-5718-06-01786-8/}{\textit{Proving primality in essentially quartic random time}}, Mathematics of Computation \textbf{76} (2007), 398--403.
\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{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{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.
\bibitem{morain} F. Morain, \href{http://www.ams.org/journals/mcom/2007-76-257/S0025-5718-06-01890-4/}{\textit{Implementing the asymptotically fast version of the elliptic curve primality proving algorithm}}, Mathematics of Computation \textbf{76} (2007), 493--505.
\end{thebibliography}

\end{document}