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

\newtheorem*{theorem}{Theorem}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.783 Elliptic Curves\hspace{220pt}Spring~2015}\\\vspace{4pt}
\textbf{Problem Set \#11\hspace{215pt}Due: 05/01/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 18--21.
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 both Problems 1 and 2, or just solve Problem 3, and then complete Problem~4, which is a survey.  Problem 1 part (d) uses a result from Problem~3 part (f) of Problem Set 10 --- contact me if you did not solve this problem and I can send you the result you need.

\subsection*{Problem 1. Mapping the CM torsor (50 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 Lecture 18, the set
\[
\EllO(\Fp)=\{j(E/\Fp): \End(E)\simeq\O\}
\]
is a $\cl(\O)$-torsor.
This means that for any pair $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 Set 11 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, using $D=-1091$.  In this case 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 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://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783%20Isogeny%20Neighbors.sagews}{Sage worksheet}, 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$, because $\alpha$ has order 17 in $\cl(D)$.  Finally, verify that the you have in fact 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.
One can enumerate the roots of polynomial whose degree is, say, 10 million, 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 on the order of $10^{1000000}$ bits in the problem you just solved.  Even reduced modulo~$p$, it would take more than $10^{10000}$ bits to write down the coefficients of this polynomial (for comparison, there are fewer than $10^{100}$ atoms in the universe).  This example might seem fanciful, but an isogeny of degree $10^{100}$ is well within the range that might be of interest in cryptographic applications.

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 do Problem 3 of Problem Set 10, don't worry, I will post a solution for this part shortly.

\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 you student ID.  Using the polycyclic presentation for $\cl(D)$, enumerate $\EllO(D)$ 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_{\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 have a choice to make, but you can make all of them consistent with your choice of $j_1$.

I don't recommend trying to write a program to make all these choices (this 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://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783%20Isogeny%20Neighbors.sagews}{Sage worksheet}).


\subsection*{Problem 2. Computing Hilbert class polynomials (50 points)}
In this problem you will implement an algorithm to compute Hilbert class polynomials using a CRT approach.
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$).
By doing this for a sufficiently large set of primes $S$, we can then use the Chinese remainder theorem to determine the integer coefficients of $H_D$.

We will use primes $p$ that are small enough for us to readily find an element $j_0$ of $\EllO(\Fp)$ by trial and error.
Once we know $j_0$, we can enumerate $\EllO(\Fp)$ using a polycyclic presentation for $\cl(\O)$, as described in Problem 3 of Problem Set 10.
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}

\begin{enumerate}[{\bf (a)}]
\item Write a program that, given a prime $p$ 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-t)P$ or $(p+1+t)P$ is zero.
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}$ than $\#E(\Fp)$ must be $p+1\pm t$, and we have a curve we can use.
Otherwise, discard it and continue.
\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 $\O$, but for now we will simply choose primes $p$ that have $v=1$, in which case $\Z[\pi]=\End(E)=\O_K$ must hold.\footnote{We should note that with $v=1$ fixed, we cannot actually prove that any such primes exist (even under the GRH), so this restriction does not yield a true algorithm.  But it works.}
With this provision, part 1 gives us an element $j_0\in\EllO(\Fp)$, namely, $j_0=j(E)$.
We can then enumerate $\EllO(\Fp)$ as in Problem 3 of Problem Set 10 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 need to apply the Chinese remainder theorem to compute $H_D\in\Z[X]$.
Let $S=p_1,\ldots,p_n$ 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$ be the corresponding coefficient of $H_D\bmod p$.
Then
\begin{equation}\label{sum}
c\equiv\sum_{i=1}^n c_ia_iM_i\bmod M.
\end{equation}
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$.
For Hilbert class polynomial we have very accurate bounds $B$ on the absolute values of their coefficients that can be derived analytically.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{1}
\item Write a program to compute the values $M_i$ and $a_i$ given the set of primes $S$.
These can be most efficiently computed using a product tree approach, but to simplify the implementation, just compute each $M_i=M/p_i$ and then compute $a_i$ as the inverse of $M_i$ modulo $p_i$.
\end{enumerate}

As each polynomial $H_D\bmod p$ is computed, we will update running totals for each coefficient $c$, accumulating the sum in \eqref{sum} as we go.  Now that all the ingredients are in place, we are ready to compute a Hilbert class polynomial.
We will use the discriminant $D=-131$ with class number h(D)=5.
The coefficients of $H_D$ have absolute values bounded by $B=2^{110}$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{2}
\item
Let $D=-131$ and $B=2^{110}$ as above.
Select a set $S$ of primes of the form $4p=(t^2-D)$ such that $\prod_{p\in S}p > 2B$, and then compute the integers $M_i$ and $a_i$ for each $p_i\in S$ as in part 2.
The class group $\cl(D)$ is generated by a prime ideal of norm 3, so we can use this as our polycyclic presentation.
For each prime $p$ in $S$ do the following:
\begin{enumerate}[1.]
\setlength{\itemsep}{0pt}
\item Find $j_0\in\EllO(\Fp)$ using part~(a).
\item Enumerate $\EllO(\Fp)$ by walking a cycle of 3-isogenies.
\item Compute $H_D\bmod p$ via \eqref{prod}.
\item Update the sum in \eqref{sum} for each coefficient of $H_D$.
\end{enumerate}
When all the primes $p\in S$ have been processed, for each coefficient of $H_D$, determine the unique integer $c\in [-M/2,M/2]$ that satisfies \eqref{sum}, and then output $H_D(X)$.

In your answer, include 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$.
\end{enumerate}

When debugging your code in part (c), you may find it helpful to use Sage to compute the Hilbert class polynomial and compute its roots in $\Fp$, so that you know exactly the values of $\EllO(\Fp)$ that you should be getting.

\subsection*{Problem 3. The Gross-Zagier formula for singular moduli (100 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 \emph{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_i-j_k\bigr),
\]
where $h_1=h(D_1)$ and $h_2=h(D_2)$, and $j_i$ and $j_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}

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 4 and 5 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 7 do the following:
\begin{enumerate}[{\bf(i)}]
\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://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783%20Norm%20Equation.sagews}{Sage worksheet} 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 \texttt{hilbert\_class\_polynomial} function to get $H_{D_1},H_{D_2}\in\Z[X]$ then coerce them into $\Fp[X]$ to find their roots).
\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 4. 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
\end{tabular}
\end{center}
\noindent
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/23 & The modular equation & & & & \\\hline 
4/28 & Main theorem of CM & & & & \\\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{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{GZ} B. Gross and D. Zagier, \href{https://eudml.org/doc/152694}{\textit{On singular moduli}}, J. Reine Angew. Math. (Crelles Journal) \textbf{355} (1984), 191--220.
\end{thebibliography}

\end{document}