\newif\ifOCW
%\OCWtrue
\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}
\hypersetup{colorlinks=true,urlcolor=blue,citecolor=blue,linkcolor=blue}
\ifOCW\usepackage{soul}\let\oldhref\href\renewcommand{\href}[2]{\oldhref{#1}{\ul{#2}}}\fi
\ifOCW\newcommand{\due}[1]{\hfill\phantom{Due: #1}}\else\newcommand{\due}[1]{\hfill{Due: #1}}\fi
\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{plain}

% 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{\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{\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{\q}{{\mathfrak q}}

\newtheorem*{theorem}{Theorem}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.783 Elliptic Curves\hfill Fall~2025}\\\vspace{4pt}
\textbf{Problem Set \#11\due{12/5/2025}}\\\vspace{-6pt}
\normalsize
\begin{picture}(5.8,.1) 
\put(0,0) {\line(1,0){5.8}}         
\end{picture}
\end{center}

\noindent\textbf{Description}: These problems are related to the material covered in Lectures 17--21.  Your solutions should be written in LaTeX and submitted as a PDF file \ifOCW\else to \href{https://www.gradescope.com/courses/1109839}{Gradescope} \fi by midnight on the date due.
\medskip

\noindent
\textbf{Instructions}: Solve any combination of problems that sum to 100 points, or \textbf{alternatively, solve any combination of problems that sum to 200 points to receive credit for two problem sets}.  In the latter case, your best scores on a subset summing to 100 points will count for this problem set and the sum of the rest will replace your worst score on any other problem set, if it would improve it.
Collaboration is permitted/encouraged, but you must identify your collaborators (including any LLMs you discussed the problem set with), as well as any references you consulted outside the \ifOCW\href{https://ocw.mit.edu/courses/mathematics/18-783-elliptic-curves-spring-2021/syllabus}{syllabus}\else\href{http://math.mit.edu/classes/18.783/2025/syllabus.html}{syllabus}\fi\ or \ifOCW\href{https://ocw.mit.edu/courses/mathematics/18-783-elliptic-curves-spring-2022/lecture-notes-and-worksheets}{lecture notes}\else\href{http://math.mit.edu/classes/18.783/2025/lectures.html}{lecture notes}\fi.  Include this information after the \textbf{Collaborators/Sources} prompt at the end of the problem set (if there are none, you should enter ``none'', do not leave it blank).
Each student is expected to write their own solutions; it is fine to discuss problems with others, but your writing must be your own.

\subsection*{Problem 1. Mapping the CM torsor (49 points)}
Let $\O$ be an imaginary quadratic order of discriminant $D$, and let $p>3$ be a prime that splits completely in the ring class field of $\O$, equivalently, a prime of the form $4p=t^2-v^2D$.
As explained in Lecture 17, the set
\[
\EllO(\Fp)=\{j(E/\Fp): \End(E)\simeq\O\}
\]
is a $\cl(\O)$-torsor.
This means that for any $j_1,j_2\in\EllO(\Fp)$, there is a unique $\alpha\in\cl(\O)$ for which $\alpha j_1=j_2$.
This has many implications, two of which we explore in this problem.

First and foremost, the $\cl(\O)$-action can be used to enumerate the set $\EllO(\Fp)$, all we need is a starting point $j_0\in\EllO(\Fp)$.
In this problem we will ``cheat" and use the Hilbert class polynomial $H_D(X)$ to do this (in Problem 2 we will find a starting point ourselves).
The polynomial $H_D(X)$ splits completely in $\Fp[X]$, and its roots are precisely the elements of $\EllO(\Fp)$.
We could enumerate $\EllO(\Fp)$ by factoring $H_D(X)$ completely, but that would not let us ``map the torsor".
We want to construct an explicit bijection from $\cl(\O)$ to $\EllO(\Fp)$ that is compatible with the group action.

Let us start with a simple example, $D=-1091$.  The class number $h(D)=17$ is prime, so $\cl(D)$ is cyclic and every non-trivial element is a generator.  For our generator, let $\alpha$ be the class of the prime form $(3,1,91)$, which acts on $\EllO(\Fp)$ via cyclic isogenies of degree 3: each $j\in\EllO(\Fp)$ is 3-isogenous\footnote{When we say that $j_1$ and $j_2$ are 3-isogenous, we are referring to isomorphism classes of elliptic curves over $\Fpbar$.  There are 3-isogenous curves $E_1/\Fp$ and $E_2/\Fp$ with $j_1=j(E_1)$ and $j_2=(E_2)$, but one must be careful to choose the correct twists.} to the $j$-invariant $\alpha j$.
This means that $\Phi_3(j,\alpha j)=0$ for all $j\in\EllO(\Fp)$, where $\Phi_3(X,Y)=0$ is the modular equation for~$X_0(3)$.

To enumerate $\EllO(\Fp)$ as $j_0,j_1,j_2,\ldots$, with $j_k=\alpha^k j_0$, we start by identifying $j_1$ is a root of the univariate polynomial $\Phi_3(j_0,Y)$.
Now $\left(\frac{D}{3}\right)=1$ in this case, so by part (d) of problem 3 on Problem Set 10 there are two ideals of norm 3 in $\cl(D)$, both of which act via 3-isogenies; the other one corresponds to the form $(3,-1,91)$, the inverse of $\alpha$ in $\cl(\O)$.  Thus there are at least two roots of $\Phi_3(j_0,Y)$ in $\Fp$, but provided that we pick the prime $p$ so that $3$ does not divide $v$, there will be only two $\Fp$-rational roots.

There are methods to determine which of these two roots ``really" corresponds to the action of $\alpha$, but for now we disregard the distinction between $\alpha$ and $\alpha^{-1}$; this ultimately depends on how we embed $\Q(\sqrt{-1091})$ into $\C$ in any case.  Let us arbitrarily designate one of the $\Fp$-rational roots of $\Phi_3(j_0,Y)$ as $j_1$.  To determine $j_2$, we now consider the $\Fp$-rational roots of $\Phi_3(j_1,Y)$.  Again there are exactly two, but we already know one of them: $j_0$ must be a root, since $\Phi_3(X,Y)=\Phi_3(Y,X)$.
So we can unambiguously identify $j_2$ as the \emph{other} $\Fp$-rational root of $\Phi_3(j_1,Y)$, equivalently, the unique $\Fp$-rational root of $\Phi_3(j_1,Y)/(Y-j_0)$.

\begin{enumerate}[{\bf(a)}]
\item
Let $D=-1091$, and let $t$ be the least odd integer greater than $1000N$ for which $p=(t^2-D)/4$ is prime, where $N$ is the last three digits of you student ID.
Use the Sage function \texttt{hilbert\_class\_polynomial} to compute $H_D(X)$, then pick a root $j_0$ of $H_D(X)$ in~$\Fp$ (you will need to coerce $H_D$ into the polynomial ring~$\Fp[X]$ to do this).
Using the function \texttt{isogeny\_nbrs} implemented in this \href{https://cocalc.com/AndrewVSutherland/18.783Fall2025/IsogenyNeighbors}{Sage notebook}, enumerate the set $\EllO(\Fp)$ as $j_0,j_1,j_2,\ldots $ by walking a cycle of 3-isogenies starting from $j_0$, as described above, so that $j_k=\alpha^k j_0$ (assuming that your arbitrary choice of $j_1$ was in fact $j_1=\alpha j_0$).  You should find that the length of this cycle is $17$, since $\alpha$ has order 17 in $\cl(D)$.  Finally, verify that you have actually enumerated all the roots of $H_D(X)$.

\item
Let $D$, $p$, and $j_0$ be as in part (a), and let $\beta\in\cl(D)$ be the class of the prime form $(7,1,39)$.  Compute $k=\log_\alpha\beta$. Enumerate $\EllO(\Fp)$ again as $j_0',j_1',j_2',\ldots$, starting from the same $j_0'=j_0$ but this time use the action of $\beta$, by walking a cycle of 7-isogenies.  Rather than choosing $j_1'$ arbitrarily, choose $j_1'$ in a way that is consistent with the assumption $j_1=\alpha j_0$ in part (a): i.e., choose $j_1'$ so that $j_1'=\beta j_0=\alpha^k j_0 = j_k$.  Then verify that for all $m=1,2,3,\ldots,16$ we have $j_m'=\beta^m j_0 = \alpha^{km} j_0 = j_{km}$, where the subscript $km$ is reduced modulo $|\alpha|=17$.
\end{enumerate}

You should find the results of parts (a) and (b) remarkable (astonishing even).
\emph{A priori}, there is no reason to think that there should be a relationship between a cycle of 3-isogenies and a cycle of 7-isogenies.

The fact that we can use the modular polynomials $\Phi_\ell$ to enumerate the roots of $H_D$ is extremely useful.
It allows us to enumerate the roots of polynomials with degrees in the millions, simply by finding roots of polynomials of very small degree (typically one can use $\Phi_\ell$ with $\ell < 20$).
We can also use the CM torsor to find zeros of $\Phi_\ell$, even when~$\ell$ is ridiculously large.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{2}
\item
Let $\ell$ be the least prime greater than $10^{100} N$ for which $\left(\frac{D}{\ell}\right)=1$, where $N$ is the last three digits of your student ID.
Determine the $\Fp$-rational roots of $\Phi_\ell(j_0,Y)$.
\end{enumerate}

For reference, the total size of the polynomial $\Phi_\ell\in\Z[X,Y]$ is roughly $6\ell^3\log\ell$ bits, which is more than $10^{300}$ bits in the problem you just solved.  Even reduced modulo~$p$, it would take more than $10^{200}$ bits to write down the coefficients of this polynomial (for comparison, there are fewer than $10^{100}$ atoms in the observable universe).  This example might seem fanciful, but an isogeny of degree $10^{100}$ is well within the range of cryptographic interest.

Now for a slightly more complicated example, where the class group is not a cyclic group of prime order.
Let $D=-5291$.  In this case $h(D)=36$ and the class group $\cl(D)$ is isomorphic to $\Z/2\Z\times \Z/18\Z$.  In Problem 3 of Problem Set 10 you computed a polycyclic presentation $\vec{\alpha}$, $r(\vec\alpha)$, $s(\vec\alpha)$ for $\cl(D)$, which should involve generators $\vec{\alpha}=(\alpha_1, \alpha_2, \alpha_3)$, of norms 3, 5, and~7.  If you did not solve Problem 3 of Problem Set 10, you can email me for a solution.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{3}
\item
Let $D=-5291$, and let $t$ be the least odd integer greater than $1000N$ for which $p=(t^2-D)/4$ is prime, where $N$ is the last three digits of your student ID.  Using the polycyclic presentation for $\cl(D)$, enumerate $\EllO(\Fp)$ starting from a $j$-invariant $j_0$ obtained as a root of $H_D$.  Your enumeration $j_0,j_1,j_2,\ldots, j_{35}$ should have the property that the element $\beta\in\cl(\O)$ whose action sends $j_0$ to $j_k$ satisfies $k=\log_{\vec\alpha}\beta$, subject to the assumption that $j_1=\alpha_1j_0$.
\end{enumerate}

Here are a few tips on part (d).  You will compute $j_0,\ldots,j_{r_1-1}$ using 3-isogenies, but to compute $j_{r_1}$ you will need to compute a 5-isogeny from $j_0$.
When choosing $j_{r_1}$ as a root of $\Phi_5(j_0,Y)$, make this choice consistent with the assumption $j_1=\alpha_1j_0$ by using the fact that $s_2 = \log_{\vec{\alpha}}\alpha_2^{r_2}$ (assuming $s_2\ne 0$, which is true in this case).
When you go to compute $j_{r_1+1}$, you will need to choose a root of $\Phi_3(j_{r_1},Y)$.  Here you can make the choice consistent with the fact that $\cl(\O)$ is abelian, so the action of $\alpha_1\alpha_2$ should be the same as the action of $\alpha_2\alpha_1$.
Similar comments apply throughout; any time you start a new isogeny cycle, you must make a choice, but you can make all of your choices consistent with your initial choice of $j_1$.

I don't recommend writing code to make all these choices (it can be done but it is a bit involved), it will be easier and more instructive to work it out by hand, using Sage to enumerate paths of $\ell$-isogenies as required (you can use the function \texttt{isogeny\_path} in this \href{https://cocalc.com/AndrewVSutherland/18.783Fall2025/IsogenyNeighbors}{Sage notebook}).


\subsection*{Problem 2. Computing Hilbert class polynomials (49 points)}
In this problem you will implement an algorithm to compute Hilbert class polynomials using an explicit CRT approach and then use it to construct an elliptic curve over a finite field $\Fq$ via the CM method.
The plan is to compute $H_D$ modulo primes $p$ that split completely in the ring class field for the order $\O$ of discriminant $D$ (primes of the form $4p=t^2-v^2D$).
If we do this for a sufficiently large set of primes $S$, we can use the Chinese remainder theorem to explicitly determine the coefficients of $H_D$.  For any prime (or prime power) $q$ that satisfies the norm equation $4q=t^2-v^2D$ we can then use a root of $H_D$ in $\Fq$ to construct an elliptic curve $E/\Fq$ with $\End(E)=\O$, and in particular, with trace of Frobenius $\pm t$ and $q+1\pm t$ rational points; by taking a quadratic twist we can adjust the sign of $t$.

We will use primes $p$ that are small enough for us to readily find an element $j_0\in\EllO(\Fp)$ by trial and error.  Note that this will typically not be true of our target prime~$q$, particularly in cryptographic applications; we will use $q=2^{66}+9$ which is not of cryptographic size but still large enough to make trial and error an infeasible method for constructing an elliptic curve with $\End(E)=\O$.

Once we know one $j_0\in \EllO(\Fp)$, we can enumerate $\EllO(\Fp)$ using a polycyclic presentation for $\cl(\O)$, as described in Problem 3 of Problem Set 10.
To make our lives simpler, in this problem we will choose $\O$ so that $\cl(\O)$ is a cyclic group of prime order generated by an ideal of small prime norm so that we don't have to compute a polycyclic presentation.
This gives us a list of the roots of $H_D\bmod p$, and we can then compute
\begin{equation}\label{prod}
H_D(X)=\prod_{j\in\EllO(\Fp)}(X-j) \bmod p.
\end{equation}
Once we have computed the coefficients of $H_D\bmod p$ for sufficiently many primes $p$, we can use the CRT to compute the integer coefficients of $H_D\in \Z[X]$.

But our goal is to construct $E/\Fq$, which means we actually only need $H_D\bmod q$.  Rather than computing $H_D\in \Z[X]$ and then reducing modulo $q$, we will instead apply an explicit form of the CRT that allows us to compute $H_D\bmod q$ directly from the coefficients of $H_D\bmod p$ for sufficiently many small primes $p$.  This saves space (and a little bit of time), because for large $|D|$ the integer coefficients of $H_D$ will typically be much larger than $q$ (possibly by millions of bits).

\begin{enumerate}[{\bf (a)}]
\item Write a program that, given a prime $p>36$ and an integer $t$ finds an elliptic curve $E/\Fp$ satisfying $\#E(\Fp)=p+1\pm t$.
Do this by generating curves $E/\Fp$ with random coefficients~$A$ and $B$ satisfying $4A^3+27B^2\ne 0$.
For each curve, pick a random point $P\in E(\Fp)$ (using the \texttt{random\_point()} method), and test whether $(p+1)P=\pm tP$.
If not, discard the curve and continue.  Otherwise, compute the order $m$ of $P$ using the generic fast order algorithm provided by the Sage function \texttt{sage.groups.generic.order\_from\_multiple}.
If~$m>4\sqrt{p}$ then $\#E(\Fp)$ must be $p+1\pm t$, and we have a curve we can use.
Otherwise, try again.
\end{enumerate}

Having found a curve $E/\Fp$ whose Frobenius endomorphism $\pi$ has trace~$\pm t$, where $4p=t^2-v^2D$, then $\Z[\pi]$ and $\End(E)$ must lie in the maximal order of $K=\Q(\sqrt{D})$.  Assuming that $D$ is fundamental, the order $\O$ we are interested in is the maximal order~$\O_K$, but unless $\Z[\pi]=\O_K$ it is unlikely that $\End(E)=\O_K$.  On the next problem set we will see how to find a curve isogenous to $E$ with endomorphism ring $\O$, but for now we will simply choose primes $p$ that have $v=1$, in which case $\Z[\pi]=\End(E)=\O_K$.\footnote{With $v=1$ fixed, we cannot actually prove that any such primes exist, not even under the generalized Riemann hypothesis (GRH), so this does not yield a true algorithm in the sense that we cannot prove it terminates on all inputs.  Relaxing the constraint $v=1$ yields an algorithm that is guaranteed to work, and under GRH, one can prove it is faster than any other method known.}
With this provision, \textbf{(a)} gives us $j_0\in\EllO(\Fp)$.
We can then enumerate $\EllO(\Fp)$ as in Problem 1 and apply \eqref{prod} to compute $H_D(X)\bmod p$.

Once we have computed $H_D\bmod p$ for all the primes in $S$, we can apply the Chinese remainder theorem to compute $H_D\in\Z[X]$.
Let $p_1,\ldots,p_m$ be the primes in $S$, and let $M=\prod_{p\in S} p$.
Let $M_i=M/p_i$, and let $a_iM_i\equiv 1 \bmod p_i$.
Let $c$ denote a coefficient of $H_D$, and let $c_i=c\bmod p_i$ be the corresponding coefficient of $H_D\bmod p_i$.

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

\item Prove that
\begin{equation}\label{sum}
c\equiv\sum_{i=1}^m c_ia_iM_i\bmod M.
\end{equation}
\end{enumerate}

Provided that $M$ is big enough, say $M\ge 2B$, where $B$ is an upper bound on $|c|$, this congruence uniquely determines the integer $c$.
Using complex analytic methods, one can establish very accurate bounds $B$ on the absolute values of the coefficients of $H_D(X)$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{2}
\item Prove that if $M>4B$ and $r$ is the nearest integer to $\sum c_i a_i/p_i$, then in fact
\begin{equation}\label{sumr}
c = \sum_{i=1}^m c_ia_iM_i -rM,
\end{equation}
and show that if we put $e:=\lceil \log_2 m\rceil+2$ and define $r_i:=\lfloor 2^e c_ia_i/p_i\rfloor$, then we have $r=\lfloor 3/4 + 2^{-e}\sum r_i\rfloor$ (in other words, we only need to use $e=O(\log m)$ bits of precision when computing the sum $\sum c_ia_i/p_i$ in order to get the correct value of $r$).
\end{enumerate}
The fact that \eqref{sumr} is an identity in $\Z$ means that it also holds modulo $q$; this means that as we compute the coefficients $c_i$ of $H_D\bmod p_i$ it suffices to just accumulate the partial sums of $c_ia_iM_i$ modulo $q$ and the partial sum of the $r_i$ (we do want to compute the sums of the $r_i$ in $\Z$, but they are tiny, typically much smaller than $q$).
As each polynomial $H_D\bmod p_j$ is computed, we will update two running totals for each coefficient $c$ as we go, one for $\sum_i c_ia_iM_i\bmod q$ and one for $\sum_i r_i$.

We are now ready to compute $H_D(X)\bmod q$, where $q=2^{66}+9$, and use it to construct an elliptic curve $E/\Fq$.
We will use the discriminant $D=-2267$ with class number $h(D)=11$; the class group is necessarily cyclic, generated by a primeform of norm 7.  The coefficients of $H_D$ can be analytically proven to have absolute values bounded by $B=2^{520}$ via \cite[Lemma 8]{sut}.  As you can check using the \texttt{norm\_equation} function in this \href{https://cocalc.com/AndrewVSutherland/18.783Fall2025/NormEquation}{Sage notebook}, we have $4q=t^2-v^2D$, and for the positive choice of $t$, the integer $N=q+1+t$ is prime.  Our goal is to construct $E/\Fq$ with $\#E(\Fq)=N$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{3}
\item
Select a set $S$ of primes $p_1,\ldots,p_m$ of the form $4p=(t^2-D)$ such that $\prod_{p\in S}p > 4B$. Then compute the $a_i\bmod p_i$ as integers in $[0,p-1]$ and the products $a_iM_i$ modulo $q$ as integers in $[0,q-1]$ for each $1\le i\le m$.
For each prime $p_i$ in $S$ do the following:
\begin{enumerate}[1.]
\setlength{\itemsep}{0pt}
\item Find $j_0\in\EllO(\F_{p_i})$ using \textbf{(a)}.
\item Enumerate $\EllO(\F_{p_i})$ by walking an 11-cycle of 7-isogenies (as in Problem 1, you can use the \texttt{isogeny\_nbrs} function in this \href{https://cocalc.com/AndrewVSutherland/18.783Fall2025/IsogenyNeighbors}{Sage notebook} to do this).
\item Compute $H_D\bmod p_i$ via \eqref{prod}.
\item Update the sums $\sum_i c_ia_iM_i\bmod q$ and $\sum_i r_i$ for each coefficient of $H_D\bmod p_i$.
\end{enumerate}
When all the primes $p_i\in S$ have been processed, for each coefficient $c$ of $H_D\bmod q$, compute $r$ and then $c$ by applying \eqref{sumr} modulo $q$ via \textbf{(c)}.

In your answer, list the primes $p_i\in S$ and give a summary of the computation for the first 3 primes in~$S$, including the $j$-invariant $j_0$, the enumeration of $\EllO(\Fp)$ (in order), and the polynomial $H_D(X)\bmod p$, as well as the end result $H_D\bmod q$.
\end{enumerate}

Here are a few tips for implementing \textbf{(d)}. You will need about 40 primes for the set $S$, the smallest of which should be 569.  When debugging your code, you may find it helpful to use Sage to compute the Hilbert class polynomial $H_D$ and compute its roots in $\F_{p_i}$, so that you know exactly the values of $\EllO(\F_{p_i})$ that you should be getting.  You may find that your algorithm in \textbf{(a)} struggles a bit with some of the larger $p_i\in S$, but it should never take more than 10 or 20 seconds or so to find a suitable $E$, and in most cases it should take less than a second.  Once you get it working the entire computation for \textbf{(d)} should only take a few minutes.  This can be reduced to a few seconds by modifying the algorithm to allow $4p_i=t_i^2-v_i^2D$ with $v_i$ not necessarily equal to one and modifying the algorithm in \textbf{(a)} to use isogeny-volcano climbing to obtain $E$ with $\End(E)\simeq \O$ in situations where this is not already forced by $t_i$, but you are not required to do this.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{4}
\item Compute a root $j_0\in \F_q$ of the polynomial $H_D\bmod q$ you computed in \textbf{(d)}, construct an elliptic curve $E/\Fq$ with $j(E)=j_0$ and test whether $\#E(\Fq)=N$  by checking that $NP=0$ for a random nonzero point $P\in E(\Fq)$.  If this is not the case, replace $E$ with its quadratic twist (you can use the \texttt{quadratic\_twist} method in Sage) and check again.  Include a defining equation for your final $E$ in your write-up.
\end{enumerate}


\subsection*{Problem 3. Atkin-Morain ECPP (49 points)}
The bottleneck in the Goldwasser-Kilian elliptic curve primality proving algorithm (Algorithm 11.15 in Lecture 11) is 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 cofactor).
Atkin and Morain proposed an alternative approach that uses the CM method to construct an elliptic curve that is guaranteed to have a suitable number of points \cite{AM}.
This yields a much faster algorithm, with a heuristic running time of $\softO(n^4)$, where $n$ is the size of the input (in bits) and the $\softO$ notation ignores polylogarithmic factors of $n$. While its expected running time is not provably polynomial time, in practice it is substantially faster than even randomized versions of the AKS algorithm that also run in $\softO(n^4)$ expected time \cite{bernstein}, and is the current method of choice for proving the primality of large primes that are not of a special form.
All the primality proving records listed on this \href{https://primes.utm.edu/top20/page.php?id=27}{top 20 list} were proved using this algorithm.
\medskip

\noindent
Given a smoothness bound $B$ and probable prime $p$, the algorithm proceeds as follows:
\begin{enumerate}
\item Select a fundamental discriminant $D<-4$ 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{In practice one also uses $D=-3,-4$ but for simplicity we will ignore these.}
\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, if $q$ is larger than a bound $T\approx (\log p)^4$ 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 T$ whose primality is verified by trial division (see Lecture~12 for details).

For a fixed fundamental discriminant $D<0$, we know from the Chebotarev Density Theorem that the proportion of primes $p$ that split completely in the ring class field $L$ for the order of discriminant $D$ is $1/\Gal(L/\Q)=1/(2h(D))$, where $h(D)$ is the class number.  We also know that $h(D)\sim \sqrt{|D|}$ as $|D|\to\infty$, and that a constant proportion of all integers $D<0$ are fundamental discriminants.\footnote{Any square free $D\equiv 1\bmod 4$ certainly works, and this set already has density $3/(2\pi^2)$.}

\begin{enumerate}[{\bf (a)}]
\item Assuming the integers $m=p+1\pm t$ in step 1 are as likely as random integers to be of the form $2q$ with $q$ prime, give a heuristic upper bound on the absolute value of the discriminant $D$ chosen in step 1 of the form $\softO(n^e)$ for some $e>0$, where $n=\log p$.\footnote{Requiring $m=2q$ might seem overly restrictive, since the algorithm only requires $m=cq$ with $c>1$ $B$-smooth, but it makes no difference in the value of $e$ (unless $B$ is unrealistically large).}
\item Using your heuristic estimate in (a), compute upper bounds on the expected running times of each of steps $i=1,2,3$ of the form $\softO(n^{e_i})$; you can assume that the time to compute $H_D(X)$ is quasi-linear in $|D|$, and that the time to solve the norm equation is bounded by the expected time to compute a square root of $D$ modulo $p$ using a probabilistic algorithm (as required by Cornacchia's algorithm, see Problem Set 2).
Use these bounds to heuristically bound the expected complexity of proving that~$p$ is prime (assuming it is), including the cost of recursively proving that $q$ is prime.
\end{enumerate}
You should find that your heuristic complexity bound is substantially better than the $\softO(n^7)$ complexity of the Goldwasser-Kilian algorithm that you analyzed in Problem Set~6, but worse than $\softO(n^4)$, and that the cost is dominated by step 1.
\bigskip

In order to obtain an $\softO(n^4)$ bound we need to exploit an idea due to Jeffrey Shallit.
The key idea is to avoid the need to compute square roots of so many $D$'s modulo $p$ by restricting to discriminants of the form $D=-\ell_1\ell_2$, where $\ell_1$ and $\ell_2$ are primes in the set $S:=\{\ell\le \sqrt{M}:\ell \text{ is prime}\}$ with $M$ chosen according to the heuristic bound on $|D|$ you computed in part (a).  The strategy is to compute square roots of $\pm \ell$ modulo $p$ for all the primes in $S$ and use these to efficiently construct square roots of $D=-\ell_1\ell_2$ modulo~$p$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{2}
\item Using the fact that if it is given the square root of $D$ modulo $p$, Cornacchia's algorithm can solve the norm equation in quasi-linear time using a fast-GCD approach, derive a new heuristic estimate for the expected running time of step 1 that exploits Shallit's idea (include the cost of computing square roots of the primes $\ell \in S$).
Use this to obtain a heuristic $\softO(n^4)$ bound on the total expected time to prove that $p$ is prime using the Atkin-Morain approach.
\item Implement the Atkin-Morain ECPP algorithm described above in Sage and use it to construct a primality proof for the least probable prime $p$ greater than $2^{500}N$, where~$N$ is the last 4 digits of your student ID, using the smoothness bound $B=2^{16}$.  You are not required to implement Shallit's optimization, as it won't make much of a difference for primes of this size.

You can use the \texttt{norm\_equation} function in this \href{https://cocalc.com/AndrewVSutherland/18.783Fall2025/NormEquation}{Sage notebook} 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.
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 (it is very unlikely to be necessary).

In your write-up, do not list all the primality certificates in full.
Just give a table that lists the discriminant $D$, the $j$-invariant of the elliptic curve $E$, and the primes~$q$ for each certificate, as well as the time spent constructing each certificate.
\end{enumerate}

\subsection*{Problem 4. The Gross-Zagier formula for singular moduli (98 points)}
The $j$-invariants of elliptic curves $E/\C$ with complex multiplication are sometimes called \emph{singular moduli}, since such $j$-invariants are quite special.
As we now know, singular moduli are the roots of Hilbert class polynomials $H_D(X)$.
A famous result of Gross and Zagier \cite{GZ} gives a remarkable formula\footnote{This is not \emph{the} Gross--Zagier formula, it is their second most famous formula.  \emph{The} Gross--Zagier formula concerns the heights of Heegner points and is related to the Birch and Swinnerton--Dyer conjecture.} for the prime factorization of the norm of the difference of two singular moduli arising as roots of two distinct Hilbert class polynomials.

Let $D_1$ and $D_2$ be two relatively prime fundamental discriminants.  To simplify matters, let us assume that $D_1,D_2<-4$.
Define
\[
J(D_1,D_2) = \prod_{i=1}^{h_1}\prod_{k=1}^{h_2}\bigl(j_{1,i}-j_{2,k}\bigr),
\]
where $h_1=h(D_1)$ and $h_2=h(D_2)$, and $j_{1,i}$ and $j_{2,k}$ range over the roots of the Hilbert class polynomials $H_{D_1}(X)$ and $H_{D_2}(X)$, respectively.

\begin{enumerate}[{\bf (a)}]
\item Prove that $J(D_1,D_2)$ is an integer.
\end{enumerate}

\noindent
Gross and Zagier discovered an explicit formula for the prime factorization of $J(D_1,D_2)$.  To state it we first define two auxiliary functions.

Let us call a prime $p$ \emph{suitable} if $\left(\frac{D_1D_2}{p}\right)\ne -1$, and call a positive integer $n$ suitable if all its prime factors are suitable.
For all suitable primes $p$, let
\[
\epsilon(p) = \begin{cases}
\left(\frac{D_1}{p}\right)\quad\text{if $p\not\vert D_1$}\\
\left(\frac{D_2}{p}\right)\quad\text{if $p\not\vert D_2$}.
\end{cases}
\]
where $\kron{D}{p}$ denotes the Kronecker symbol.
\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{1}
\item Prove that $\epsilon(p)$ is well-defined for all suitable primes $p$.
\end{enumerate}
We extend $\epsilon$ multiplicatively to suitable integers $n$.
For suitable integers $m$, let
\[
F(m) = \prod_{nn'=m}n^{\epsilon(n')},
\]
where the product is over positive integers $n$ and $n'$ whose product is $m$.
\begin{theorem}[Gross--Zagier]\label{thm:GZ}
With notation as above, we have
\[
J(D_1,D_2)^2 = \prod_{\substack{x^2<D_1D_2\\ x^2\equiv D_1D_2\bmod 4}} F\left(\frac{D_1D_2-x^2}{4}\right).
\]
\end{theorem}

Note that the product on the RHS is taken over all integers $x$ (positive and negative) that satisfy the constraints (so each nonzero value of $x^2$ occurs twice).

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{2}
\item Prove that for every $x$ in the product of the theorem above, $(D_1D_2-x^2)/4$ is a suitable integer (so the formula is well-defined).
\end{enumerate}

It is not immediately obvious that the product on the right is actually an integer; in general $F(m)$ need not be.
But in fact\ every $F(m)$ appearing in the product is a (possibly trivial) prime power.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{3}
\item Let $m$ be a positive integer of the form $(D_1D_2-x^2)/4$.
Prove that $F(m)=1$ unless $m$ can be written in the form:
\[
m = p^{2a+1}p_1^{2a_1}\cdots p_r^{2a_r}q_1^{b_1}\cdots q_s^{b_s},
\]
where $\epsilon(p)=\epsilon(p_1)=\cdots =\epsilon(p_r) = -1$ and $\epsilon(q_1)=\cdots=\epsilon(q_s)=1$.  Prove that in this case we have
\[
F(m) = p^{(a+1)(b_1+1)\cdots(b_s+1)},
\]
and thus if $p$ divides $F(m)$ then $p$ is the only prime dividing $m$ with an odd exponent and $\epsilon(p)=-1$.
(Hint: see exercises 13.15 and 13.16 in \cite{cox}).

\item Prove that every prime $p$ dividing $J(D_1,D_2)$ satisfies the following:
\begin{enumerate}[{\bf (i)}]
\item $\left(\frac{D_1}{p}\right) \ne 1$ and $\left(\frac{D_2}{p}\right)\ne 1$;
\item $p$ divides an integer of the form $(D_1D_2-x^2)/4$;
\item $p\le D_1D_2/4$.
\end{enumerate}

\item Implement an algorithm to compute the prime factorization of $|J(D_1,D_2)|$, using the Gross-Zagier theorem and parts (d) and (e) above.  Then use your algorithm to compute the prime factorization of $|J(D_1,D_2)|$ for three pairs of distinct discriminants that have class number greater than 4.
Note that you can compute the class number of $D$ in Sage by creating the number field $\Q(\sqrt{D})$ using \texttt{K.<a>=NumberField(x**2-D)} and then calling \texttt{K.class\_number()}.

\item For each of the three pairs of discriminants $D_1$ and $D_2$ you selected in part (f):
\begin{enumerate}[{\bf(1)}]
\item Construct a set $S$ of primes $p_i$ that split completely in the Hilbert class fields of both $D_1$ and $D_2$ such that $\prod p_i > 10^6\cdot |J(D_1,D_2)|$.
The \texttt{norm\_equation} function in this \href{https://cocalc.com/AndrewVSutherland/18.783Fall2025/NormEquation}{Sage notebook} may be helpful.
\item For each prime $p_i\in S$, compute $J(D_1,D_2)\bmod p_i$ directly from its definition by using Sage to find the roots of $H_{D_1}(X)$ and $H_{D_2}(X)$ modulo $p_i$ and computing the product of all the pairwise differences (in Sage, use the function \texttt{hilbert\_class\_polynomial} to compute $H_{D_1},H_{D_2}\in\Z[X]$ then use the method \texttt{.change\_ring(GF(p)).roots()} to find their roots in $\Fp$).
\item Use the Chinese remainder theorem to compute $J(D_1,D_2)\in\Z$, as explained in Problem 2 above (be sure to get the sign right).
Verify that your results agree with your computations in part (f).
\end{enumerate}
\end{enumerate}

\subsection*{Problem 5. Isogeny volcanoes (98 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}

This \href{https://cocalc.com/AndrewVSutherland/18.783EllipticCurves2023/ProblemSet12}{worksheet} includes some Sage code snippets that you may find useful.

\subsection*{Problem 6. Computing modular polynomials (98 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 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 simplify matters, 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 by using a fundamental discriminant $D< -4$ 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 5 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_i(\Fp)$ with order $\ell$ by computing random $P_i=mP$ with $m=(p+1-t)/\ell^2$ for some random $P\in E(\Fp)$.  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^2Ax+d^3B$, where~$d\in \Fp^\times$ is any non-square.
\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 $\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 $D<-4$ with $(\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 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 univariate polynomial $\phi_i(Y)=\Phi_\ell(j_i,Y)=\prod_m (Y-j_{i,m})$, where the $j_{i,m}$ 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).  Use \texttt{O=QuadraticField(D).maximal\_order()} to create the order~$\O$ in Sage, then use \texttt{a=O.ideal(17).factor()[0][0]} to construct~$\a$.
\end{enumerate}


\subsection*{Problem 7. Supersingular isogeny graphs (49 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 8. Survey (2 points)}

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

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

\bigskip

\noindent
\textbf{Collaborators/Sources}:

\vspace{-8pt}
\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{cox} David A. Cox, \href{http://onlinelibrary.wiley.com/book/10.1002/9781118400722}{\textit{Primes of the form $x^{2}+ny^{2}$: Fermat, class field theory, and complex multiplication}}, second edition, Wiley, 2013.
\bibitem{kohel} David Kohel, \href{http://iml.univ-mrs.fr/~kohel/pub/thesis.pdf}{\textit{Endomorphism rings of elliptic curves over finite fields}}, PhD thesis, University of California at Berkeley, 1996.
\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.
\bibitem{GZ} B. Gross and D. Zagier, \href{https://eudml.org/doc/152694}{\textit{On singular moduli}}, J. Reine Angew. Math. \textbf{355} (1984), 191--220.
\bibitem{sut} A.V. Sutherland, \href{https://doi.org/10.1090/S0025-5718-2010-02373-7}{\textit{Computing Hilbert class polynomials with the Chinese remainder theorem.}}, Math. Comp. \textbf{80} (2011), 501--538.
\end{thebibliography}

\end{document}