\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{graphicx}
\usepackage{array}
\usepackage{color}
\usepackage{multicol}
\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}

\newcommand{\Fl}{\mathbb{F}_\ell}
\newcommand{\Fp}{\mathbb{F}_p}
\newcommand{\Fptwo}{\mathbb{F}_{p^2}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\End}{{\rm End}}
\newcommand{\M}{\textsf{M}}
\newcommand{\Gal}{{\rm Gal}}
\newcommand{\GL}{{\rm GL}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\Frob}{{\rm Frob}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\DL}{{\rm DL}^*}
\newcommand{\smat}[4]{\footnotesize{$\begin{pmatrix}#1&#2\\#3&#4\end{pmatrix}$}}
\newcommand{\pmax}{{p_{\rm max}}}
\newcommand{\qalg}[3]{\Bigl(\frac{#1,#2}{#3}\Bigr)}

\newtheorem{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{definition}{Definition}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.783 Elliptic Curves\hfill Fall~2023}\\\vspace{4pt}
\textbf{Problem Set \#6\due{10/27/2023}}\\\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 11-12.
\medskip

\noindent\textbf{Instructions}: Pick any combination of problems to solve that sums to 100 points.
Your solutions are to be written up in latex and submitted as a pdf-file \ifOCW\else to \href{https://www.gradescope.com/courses/591290}{Gradescope}\fi.

Collaboration is permitted/encouraged, but you must identify your collaborators or your group\ifOCW\else\ on \href{https://psetpartners.mit.edu}{pset partners}\fi, as well any references you consulted that are not listed in the \ifOCW\href{https://ocw.mit.edu/courses/mathematics/18-783-elliptic-curves-spring-2022/syllabus}{syllabus}\else\href{http://math.mit.edu/classes/18.783/2023/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/2023/lectures.html}{lecture notes}\fi. If there are none write ``\textbf{Sources consulted: none}'' at the top of your solutions.  Note that each student is expected to write their own solutions; it is fine to discuss the problems with others, but your writing must be your own.

The first person to spot each non-trivial typo/error in the problem sets or lecture notes will receive 1-5 points of extra credit.

In cases where your solution involves writing code, please either include your code in your write up (as part of the pdf), or the name of a notebook in your 18.783 CoCalc project containing you code (please use a separate notebook for each problem).


\subsection*{Problem 1.  A noncommutative endomorphism ring (29 points)}
Let $p=7$, and consider the finite field $\Fptwo$, which we may represent explicitly as
\[
\Fptwo\simeq \Fp[i]/(i^2+1)=\{a+bi:a,b\in\Fp\}.
\]
To create the field $\Fptwo$ in Sage using this particular representation, use
\begin{lstlisting}
F7.<x>=PolynomialRing(GF(7))
F49.<i>=GF(49,modulus=x^2+1)
\end{lstlisting}
Now consider the elliptic curve $E/\Fptwo$ defined by
\[
y^2=x^3+(1+i)x.
\]
The group of $\Fptwo$-rational points on $E$ is isomorphic to $\Z/6\Z \oplus \Z/6\Z$ and is
generated by the affine points
\[
P_1 = (i,i), \quad P_2=(i+2,2i),
\]
which you can construct in Sage using \texttt{P1=E(i,i)} and \texttt{P2=E(i+2,2*i)}.
Let $\pi_E$ denote the Frobenius endomorphism of $E$.

\begin{enumerate}[{\bf (a)}]
\item
Prove that $\pi_E=7$ in $\End(E)$.
\end{enumerate}
Since $\pi_E$ corresponds to an integer in $\End(E)$, you might be tempted to conclude that $\End(E)\simeq\Z$.
But this is far from true.
\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{1}
\item
Show that the $p$-power Frobenius map $\pi$ of degree $p=7$ does not lie in $\End(E)$.
\item
Prove that nevertheless $\End(E)$ does contain an endomorphism $\alpha$ of degree $7$ by exhibiting an explicit rational map $\alpha\colon E\to E$ that satisfies $\alpha^2=-7$.
\item
Now find an endomorphism $\beta$ that satisfies $\beta^2=-1$ (give $\beta$ explicitly).
\item
Prove that $\alpha$ and $\beta$ do not commute, but $\alpha\beta=-\beta\alpha$ holds.\\
Conclude that $\End^0(E)$ is a quaternion algebra.
\end{enumerate}

\subsection*{Problem 2.  The image of Galois (69 points)}
Let $E/\Q$ be an elliptic curve, let $\ell$ be a prime, and let $K=\Q(E[\ell])$ be the associated \emph{$\ell$-torsion field} obtained by adjoining the coordinates of all the points in the $\ell$-torsion subgroup $E[\ell]$ to $\Q$.  As you proved in Problem Set 3, the $\ell$-torsion field $K$ is a Galois extension of $\Q$, and the Galois group $\Gal(K/\Q)$ acts linearly on the vector space
\[
E[\ell]\ \simeq\ \Z/\ell\Z\oplus \Z/\ell\Z\ \simeq\ \Fl^2.
\]
This induces a group homomorphism
\[
\rho_{E,\ell}:\Gal(K/\Q)\to \Aut(E[\ell])\simeq \GL_2(\Fl)
\]
that maps each field automorphism $\sigma\in\Gal(K/\Q)$ to an element of $\GL_2(\Fl)$ that we may view as an invertible $2\times 2$ matrix with coefficients in $\Fl$, once we have fixed a choice of basis for $E[\ell]\simeq \Fl^2$.

As you may recall, a homomorphism from a group $G$ to a group of linear transformations is called a (linear) \emph{representation} of $G$.
The map $\rho_{E,\ell}$ is a representation of the group $\Gal(K/\Q)$, known as the \emph{mod-$\ell$ Galois representation} attached to $E$.\footnote{One can replace the $\ell$-torsion field $K=\Q(E[\ell])$ with any algebraic extension of $K$, including an algebraic closure of $\Q$, but the representation is still determined by its restriction to $K$.}

For each prime $p\ne\ell$ where $E$ has good reduction there is a corresponding \emph{Frobenius element} $\Frob_p\in \Gal(K/\Q)$.  To construct $\Frob_p$ one picks a prime ideal $\p$ of the ring of integers $\O_K$ (the integral closure of $\Z$ in $K$) that divides the ideal $p\O_K$, and then considers the \emph{decomposition subgroup} $D_\p :=\{\sigma\in \Gal(K/\Q):\sigma(\p)=\p\}$.  Our conditions on $p$ ensure that $D_\p$ is naturally isomorphic to $\Gal(\FF_\p/\Fp)$, where $\FF_\p:=\O_K/\p$ is the \emph{residue field} of $\p$, which necessarily contains $\Fp$ as a subfield (because $\p$ contains $p\O_K$); the isomorphism is given by restricting $\sigma\in D_\p$ to $\O_K$ and reducing modulo $\p$ to obtain an automorphism of $\O_K/\p=\FF_\p$.
The Galois group $\Gal(\FF_\p/\Fp)$ is cyclic, generated by the Frobenius automorphism $\pi\colon x\mapsto x^p$, and we take $\Frob_p$ to be the inverse image of $\pi$ under the natural isomorphism $D_\p\overset{\sim}{\longrightarrow}\Gal(\FF_\p/\Fp)$.
Now $\Frob_p$ depends on our choice of the prime ideal $\p$ dividing $p\O_K$, but different choices lead to conjugate elements, and since the representation $\rho_{E,\ell}\colon \Gal(K/\Q)\simeq\GL_2(\Fl)$ is only determined up to conjugacy in any case (it depends on a choice of basis for $E[\ell]$), this ambiguity will not concern us.

The property of $\Frob_p$ that is relevant to us here is that we can make the identification
\[
\rho_{E,\ell}(\Frob_p)=\pi_\ell\in\End(E_p[\ell])\simeq \GL_2(\Fl).
\]
Here $E_p/\Fp$ is the reduction of the elliptic curve $E/\Q$ modulo $p$ obtained by reducing the coefficients of an integral equation $y^2=x^3+Ax+B$ for $E/\Q$ modulo $p$, and $\pi_\ell\in \End(E_p[\ell])$ is the restriction of the Frobenius endomorphism $\pi_{E_p}$ to the $\ell$-torsion subgroup $E_p[\ell]$.
Both sides of the equality above are determined only up to conjugacy (each depends on a choice of basis), so there is no harm in making this identification, provided that we keep this in mind.
The key point is that the conjugacy class of $\rho_{E,\ell}(\Frob_p)=\pi_\ell\in\GL_2(\Fl)$ is uniquely determined.
In particular, we have
\[
\tr \rho_{E,\ell}(\Frob_p)\equiv \tr \pi_{E_p}\bmod \ell\qquad\text{and}\qquad \det\rho_{E,\ell}(\Frob_p)\equiv p\bmod \ell.
\]
(recall that we have assumed $p\ne \ell$).

The Chebotarev density theorem implies that for any conjugacy class $C$ of $\Gal(K/\Q)$, the proportion of primes $p$ (over $p\le B$ as $B\to\infty$) for which $\Frob_p$ lies in $C$ is exactly  $\#C/\#\Gal(K/\Q)$
Asymptotically, we can think of each prime $p$ as being assigned a uniformly random Frobenius element $\Frob_p\in\Gal(K/\Q)$ which is mapped by $\rho_{E,\ell}$ to a uniformly random element of the image of $\rho_{E,\ell}$ in $\GL_2(\Fl)$.
For a typical elliptic curve $E/\Q$, the representation $\rho_{E,\ell}$ is surjective and its image is all of $\GL_2(\Fl)$, but this is not always the case.
Number theorists (and others) are very interested in understanding these exceptional cases.
The image of $\rho_{E,\ell}$ has a direct impact on the statistical behavior of $E_p[\ell]$ as $p$ varies.
For instance, the proportion of primes $p$ for which $E_p[\ell] = E_p(\Fp)[\ell]$ is precisely $1/\#\im \rho_E$, since this occurs if and only if $\rho_E(\Frob_p)=\pi_\ell$ is the identity.

In this problem you will attempt to determine the image of $\rho_{E,\ell}$ for various elliptic curves $E/\Q$ by analyzing the statistics of $\pi_\ell$ as $p\ne \ell$ varies over primes of good reduction, by comparing these statistics to the corresponding statistics for various candidate subgroups of $\GL_2(\Fl)$.

\begin{enumerate}[{\bf(a)}]
\item Prove that for $\ell=2$ the image of $\rho_{E,2}$ in $\GL_2(\FF_2)$ is isomorphic to the Galois group of the splitting field of the cubic $f(x):=x^3+Ax+B$.
Conclude that (up to conjugacy) every possible subgroup of $\GL_2(\FF_2)$ arises as the image of $\rho_{E,2}$ for some elliptic curve $E/\Q$ and give an explicit example of each case.
\end{enumerate}

\noindent
For $\ell > 2$, not every subgroup of $\GL_2(\Fl)$ can arise as the image of $\rho_{E,\ell}$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{1}
\item Prove that there exists a set of primes $p$ of good reduction for $E$ whose reductions modulo $\ell$ generate $(\Z/\ell\Z)^\times$ (this fact is implied by Dirichlet's theorem on primes in arithmetic progressions, and by the Chebotarev density theorem, but you should give an elementary argument that does not rely on these results).
Conclude that the image of $\rho_{E,\ell}$ must contain elements of every possible determinant (all of $\Fl^\times$).
\end{enumerate}

\noindent
For $\ell=3$ there are, up to conjugacy, 9 candidate subgroups $G$ of $\GL_2(\FF_3)$ for the image of~$\rho_{E,3}$.
These are listed in Table 1, and can also be found in this \href{https://cocalc.com/AndrewVSutherland/18.783EllipticCurves2023/ProblemSet6Problem2}{Sage notebook}.

\begin{center}
\begin{tabular}{llll}
group& order & description& generators\\\hline\vspace{-8pt}
&&&\\\vspace{2pt}
$C_2$& 2 & cyclic & \smat{2}{0}{0}{1}\\\vspace{2pt}
$D_2=C_2^2$& 4 & dihedral & \smat{2}{0}{0}{1}, \smat{2}{0}{0}{2}\\\vspace{2pt}
$D_3\simeq S_3$& 6 & dihedral & \smat{1}{1}{0}{2}, \smat{1}{0}{0}{2}\\\vspace{2pt}
$D_3'\simeq S_3$& 6 & dihedral & \smat{2}{1}{0}{1}, \smat{2}{0}{0}{1}\\\vspace{2pt}
$C_8$& 8 & cyclic & \smat{1}{1}{1}{0}\\\vspace{2pt}
$D_4$& 8 & dihedral & \smat{2}{0}{0}{1}, \smat{0}{2}{1}{0}\\\vspace{2pt}
$D_6$& 12 & dihedral & \smat{1}{2}{1}{0}, \smat{0}{1}{1}{0}\\\vspace{2pt}
$Q_{16}$& 16 & semi-dihedral & \smat{1}{1}{2}{1}, \smat{0}{1}{1}{0}\\\vspace{2pt}
$\GL_2(\FF_3)$ & 48 & general linear & \smat{2}{0}{0}{1}, \smat{2}{1}{2}{0}\\\hline
\end{tabular}
\medskip

Table 1. Candidates for the image of $\rho_{E,3}$ in $\GL_2(\FF_3)$.
\end{center}

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{2}
\item The determinant $\det A$, trace $\tr A$, and multiplicative order $|A|$ of a matrix $A$ in $\GL_2(\FF_\ell)$ are invariant under conjugation.
Prove that the pair $(\det A,\tr A)$ does not determine the conjugacy class of $A$ in $\GL_2(\FF_3)$, but the triple $(\det A,\tr A,|A|)$ does.
\end{enumerate}

\noindent
Part (c) implies that we can get more information about $\pi_\ell$ if, in addition to computing its trace, we also compute its multiplicative order in the ring $\End(E_p[\ell])$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{3}
\item Devise and prove a criterion for computing the order of $\pi_2$ in $\GL_2(\FF_2)$ based on the number of roots the cubic $f(x)$ has in $\Fp$, where $y^2=f(x)$ is the Weierstrass equation for $E$.

\item
Modify the function \texttt{trace\_mod} that was used in our implementation of Schoof's algorithm in Lecture 8 (which can be found in this \href{https://cocalc.com/AndrewVSutherland/18.783EllipticCurves2023/SchoofsAlgorithm}{Sage notebook}) so that it also computes the order of $\pi_\ell$ and returns both the trace $t_\ell$ and the order $|\pi_\ell|$ of $\pi_\ell$.

\textbf{Important}: The order of $\pi_\ell$ must be computed modulo the full division polynomial~$\psi_\ell$, not modulo one of its factors.
So compute $|\pi_\ell|$ before computing $q_\ell$, which is the first place where a division-by-zero error could occur, causing $h$ to be replaced by a proper factor.
Also, be sure to compute $|\pi_\ell|$ only the first time through the loop when you know that $h=\psi_\ell$, don't accidentally recompute it if the loop repeats.

Now address the first part of (c) in a different way: pick an elliptic curve $E/\Q$ and find two primes $p$ and $p'$ for which $\pi_3\in\End(E_p[3])$ and $\pi_3'\in\End(E_{p'}[3])$ have the same characteristic polynomial but different orders in $\GL_2(\FF_3)$.

\item
Write a program that, given an elliptic curve $E$, a prime $\ell$, and an upper bound~$N$, enumerates the primes $p\le N$ distinct from $\ell$ for which $E$ has good reduction,
and for each $E_p$, computes the triple $(\det \pi_\ell, \tr \pi_\ell, |\pi_\ell|)$.
You can use \texttt{prime\_range(N+1)} to efficiently enumerate primes $p\le N$.
Keep a count of how often each distinct triple occurs (use a dictionary, as in the \texttt{group\_stats} function in this \href{https://cocalc.com/AndrewVSutherland/18.783EllipticCurves2023/ProblemSet6Problem2}{Sage notebook}).
Normalize the counts by dividing by the number of primes $p$ you used, yielding a ratio for each triple.

For $\ell=3$, use your program to provisionally determine the isomorphism class of the image of $\rho_{E,3}$ for each of the ten elliptic curves below, by comparing the statistics computed by your program with the corresponding statistics for each of the 8 candidate subgroups of $\GL_2(\FF_3)$.  With $N$ around 5000 or 10000 you should be able to easily distinguish among the possibilities.
The curves below are also listed in the notebook linked to above.


\begin{center}
\begin{tabular}{ll}
$y^2=x^3+x$ & $y^2=x^3+1$\\
$y^2 = x^3+432$ & $y^2=x^3+x+1$\\
$y^2=x^3+21x+26$ & $y^2=x^3-112x+784$\\
$y^2=x^3-3915x+113670$ &$y^2=x^3-3348-74547$\\
 $y^2=x^3+5805x-285714\qquad\qquad$&$y^2=x^3+652509x-621544482$\\
\end{tabular}
\end{center}

\item Your computations in part \textbf{(f)} should find two curves with $\im \rho_{E,3}\simeq S_3$, which could be either of the groups labelled $D_3$ and $D_3'$ in teh table above..  These nonconjugate subgroups of $\GL_2(\FF_3)$ cannot be distinguished by sampling Frobenius elements because they have exactly the same distribution of $\GL_2(\FF_3)$-conjugacy classes.  Show that you when $\im \rho_{E,3}\simeq S_3$ you can determine whether $\im\rho_{E,3}$ is conjugate to $D_3$ or $D_3'$ by computing the torsion subgroup of $E(\Q)$, which you can do in Sage using \texttt{E.torsion\_subgroup()}. Use this to determine which of the two curves in \textbf{(f)} with $\im \rho_{E,3}\simeq S_3$ corresponds to $D_3$ and which corresponds to $D_3'$, assuming that we view matrices in $\GL_2(\FF_3)$ as acting on the left.

\item
Note that if a given triple $(\det \pi_3, \tr \pi_3, |\pi_3|)$ occurs for some $E_p$ but does not occur in a candidate subgroup $G\subset\GL(\FF_3)$,  you can immediately rule out $G$ as a possibility for the image of $\rho_{E,3}$.
Analyze the 8 candidate subgroups in Table 1 to find a pair of triples that arise in $\GL_2(\FF_3)$ but do not both arise in any of its proper subgroups.
If for a given curve $E/\Q$ you can find both of these triples for some $E_{p_1}$ and $E_{p_2}$, then you have unconditionally \emph{proved} that $\rho_{E,3}$ is surjective.

Use this to devise an algorithm that attempts to prove $\rho_{E,3}$ is surjective.
Your algorithm should return \texttt{true} as soon as it can determine $\im\rho_{E,3}=\GL_2(\FF_3)$ (this should happen quite quickly, if it is true).
If this fails to happen after computing triples for $E_p$ for every prime up to, say, $10000$, then your algorithm should give up and return \texttt{false}.
You can think of this as a Monte Carlo algorithm with one-sided error: the ``randomness" comes from the assumption that the Frobenius elements $\Frob_p$ is uniformly and independently distributed over $\Gal(K/\Q)$ as $p$ varies.
If your program returns \texttt{true}, then $\rho_{E,3}$ is definitely surjective; if it returns \texttt{false} it is almost certainly not surjective, but there is a small probability of error.
Give an upper bound on the probability of error under the assumption that Frobenius elements are independent and uniformly distributed.

\item Using \texttt{ZZ.random\_element(-100,100)}, generate random elliptic curves $E/\Q$ of the form $y^2=x^3+Ax+B$, with $A$ and $B$ uniformly distributed over the interval $[-100,100]$.
Excluding cases where $AB(4A^3+27B^2)=0$, use your program to test whether the mod-3 Galois representation $\rho_{E,3}$ is surjective or not.  List five curves for which your program returns \texttt{false}, and provisionally identify the image of $\rho_{E,3}$ in each such case as in part 3 above (you may need to test a few thousand curves).
\end{enumerate}


\subsection*{Problem 3. ECPP (69 points)}
Let us define an \emph{elliptic curve primality proof} (ECPP) for $p$ as a sequence of \emph{certificates} $C_1,C_2,\ldots,C_k$, where each certificate $C_i$ is of the form $(p_i,A_i,B_i,x_i,y_i,p_{i+1})$ with $p_1=p$ and $p_{k+1}<(\log p)^4$.
In each certificate $C_i$, the primes $p_i$ and $p_{i+1}$ satisfy
\begin{equation}\label{eq:pibound}
(\sqrt[4]{p_i}+1)^2 < p_{i+1} < (\sqrt{p_i}+1)^2/2,
\end{equation}
and $P_i=(x_i,y_i)$ is a point of order $p_{i+1}$ on $E_i\colon y^2=x^3+A_ix+B_i$ over $\mathbb{F}_{p_i}$.

\begin{enumerate}[{\bf (a)}]
\item
Let $p$ be the least prime greater than $2^{128}\cdot N+3^{64}$, where $N$ is the first four digits of your student ID (use the \texttt{next\_prime} function in Sage to compute $p$).
Construct a short elliptic curve primality proof for $p$; this means each prime $p_{i+1}$ should be close to the lower bound in \eqref{eq:pibound} (you should not need more than 6 or 7 certificates).
Note: the Goldwasser-Kilian algorithm typically will \textbf{not} produce a proof this short, it will have $p_{i+1}$ closer to the upper bound in \eqref{eq:pibound}, so you will need to do something slightly different.
\item
Give an algorithm for verifying an elliptic curve primality proof and analyze its complexity.  Express your answer solely in terms of $n=\log p$ and assume the worst-case (so the proof might not be as short as the one you generated in (a)).
\item
Analyze the asymptotic complexity of constructing an elliptic curve primality proof using the Goldwasser-Kilian algorithm given in class, under the heuristic assumption that the orders of random elliptic curves over $\Fp$ have factorizations comparable to random integers in the interval $[p,2p]$.  Assume that trial division and the Miller-Rabin test are used for attempted factorizations.
Use an $O(n^5\log\log n)$ complexity bound for point-counting via Schoof's algorithm.
\item
Now suppose that you want to construct an elliptic curve primality proof that can always be verified in $O(n\M(n))$ time, where $n=\log p$.
Under the heuristic assumption above, give a probabilistic algorithm for constructing such a proof whose expected running time is bounded by $L_p[\alpha,c]$, using the smallest value of $\alpha$ that you can (hint: you can make $\alpha < 1/2$).
Your answer should include a high-level description of the algorithm and a (heuristically proven) bound on its complexity.
\end{enumerate}

\subsection*{Problem 4. Pomerance proofs (69 points)}
A \emph{Pomerance proof} is a special form of an elliptic curve primality proof that involves just a single certificate $(p,A,x_0,k)$ and uses a Montgomery curve\footnote{See the last few sections of the notes from Lecture 10 for information about Montgomery curves.} $By^2=x^3+Ax^2+x$ over $\Fp$ on which there is a point $(x_0,y_0)$ of point of order $2^k > (\sqrt[4]{p}+1)^2 \ge 2^{k-1}$.  Neither the $y$-coordinate nor $B$ is needed to verify the certificate (no matter what $x_0^3+Ax_0^2+x_0$ is, there exists a nonzero $B$ and a $y_0$ that will work and the verifier does not need to know what they are in order to double a point in Montgomery coordinates, see Section 10.9 of the Lecture notes).  But the verifier should check that $\gcd(A^2-4,p)=1$ (to ensure that the curve is not singular), and that $\gcd(z_{k-1},p)=1$ and $z_k=0\bmod p$, where $z_n$ is the $z$-coordinate of $2^n(x_0:y_0:z_0)$.

Every prime $p$ has a Pomerance proof, but for a general prime $p$ no efficient algorithm is known for finding one.
In this problem you will develop a very efficient algorithm to construct a Pomerance proof for primes of a special form.
\bigskip


Let us first convince ourselves Pomerance proofs actually do prove primality, and that every sufficiently large prime has a Pomerance proof;
for the latter we need the following theorem, which we will prove later in the course.

\begin{theorem}
Let $p$ be a prime.  For every integer $N$ in the Hasse interval
\[
\mathcal H(p) = [p+1-2\sqrt{p},\ p+1+2\sqrt{p}]
\]
there exists an elliptic curve $E/\Fp$ for which $E(\Fp)$ is a cyclic group of order $N$.
\end{theorem}

\begin{enumerate}[{\bf (a)}]
\item Show that Pomerance certificates $(p,A,x_0,k)\in \Z_{>0}^4$ exist only for prime integers $p$.
\item Using the theorem above, prove that every prime $p>31$ has a Pomerance proof.
\end{enumerate}

\noindent
Now let $E$ be the elliptic curve $y^2=x^3+8$ over $\Fp$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{2}
\item
Using the formula $\#E(\Fp)=p+1+\sum_{x\in\Fp}\left(\frac{x^3+8}{p}\right)$, prove that for every odd prime $p\equiv 2\bmod 3$ we have $\#E(\Fp)=p+1$.
\item
Prove that for any prime $p\equiv 11\bmod 12$ the curve $E/\Fp$ can be put in Montgomery form $By^2=x^3+Ax^2+x$.
Give a deterministic algorithm that computes $A$ and $B$ in time $O(n\M(n))$, where $n=\log p$.
\item
Design a Las Vegas algorithm that takes as input an integer $p=3\cdot 2^mc-1$ with $c$ odd and $2^m > (\sqrt[4]{p}+1)^2$ and outputs a Pomerance proof for prime $p$ and a Miller-Rabin witness for composite $p$.  Analyze the expected running time of your algorithm as a function of $n=\log p$.
\item
Implement your algorithm and use it to construct a Pomerance proof for a prime of the form $p=2^k\cdot 3^m-1$ that is greater than $2^{1000}$.  Be sure to format you answer so that all of the digits in the certificate you construct fit on the page.

\item As noted above, no efficient algorithm is known for constructing Pomerance proofs in general.
On the other hand, there certainly \emph{is} an algorithm; for example, one could simply enumerate all the possible certificates (clearly a finite set) and attempt to verify them.
But you can certainly do better than this.
Give the most efficient algorithm you can come up with for constructing a Pomerance proof for a given prime $p>31$ and bound its complexity.
Your algorithm need not be deterministic, and you should feel free to assume any heuristics that you believe are reasonable.
\end{enumerate}

\subsection*{Problem 5. Quaternion algebras (69 points)}
Throughout this problem $k$ is a field whose characteristic is not $2$, and a \emph{division $k$-algebra} is a $k$-algebra that is a division ring (every nonzero element is invertible).
Recall that a \emph{quaternion algebra} over $k$ is a $k$-algebra $H$ with elements $\alpha,\beta\in H$ satisfying $\alpha^2,\beta^2\in k^\times$ and $\alpha\beta=-\beta\alpha$ such that $1,\alpha,\beta,\alpha\beta$ is a basis for $H$ as a $k$-vector space.
The \emph{Hamilton quaternions} $\mathbb H$ are the quaternion algebra over $\R$ with $\alpha^2=\beta^2=-1$.


\begin{enumerate}[{\bf (a)}]
\item Show that any $k$-algebra generated by elements $\alpha,\beta$ satisfying $\alpha^2,\beta^2\in k^\times$ and $\alpha\beta=-\beta\alpha$ is a quaternion algebra (in particular, we don't need to require that $1,\alpha,\beta,\alpha\beta$ are a basis, this follows from the relations they satisfy).
\end{enumerate}

\noindent
For $a,b\in k^\times$, let $\qalg{a}{b}{k}$ be the quaternion algebra $k(\alpha,\beta)$ with $\alpha^2=a$, $\beta^2=b$, $\alpha\beta=-\beta\alpha$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{1}
\item Show that $\qalg{a}{b}{k}=\qalg{b}{a}{k}=\qalg{a}{-ab}{k}=\qalg{b}{-ab}{k}$ and $\qalg{a}{b}{k}=\qalg{ac^2}{bd^2}{k}$ for $c,d\in k^\times$.
Then show that $\qalg{1}{1}{k}\simeq \rm{M}_2(k)$ (the $2\times 2$ matrix ring over $k$).
Conclude that when $k$ is algebraically closed all quaternion algebras over $k$ are isomorphic.
\item Show over $k=\R$ every quaternion algebra $H$ is isomorphic to ${\rm M}_2(\R)$ or $\mathbb{H}$, the latter occurring if and only if $H=\qalg{a}{b}{\R}$ with $a,b<0$.
\end{enumerate}

\noindent
A \emph{central} $k$-algebra is a $k$-algebra with center $k$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{3}
\item Show that quaternion $k$-algebras are central $k$-algebras.
\end{enumerate}

\noindent
Recall that an \textit{involution} of a $k$-algebra $H$ is a ring involution (anti-isomorphism that is its own inverse) that fixes $k$.
An involution $\alpha\mapsto \hat\alpha$ of a $k$-algebra $H$ is \emph{standard} if $\alpha\hat\alpha\in k$ for all $\alpha\in H$.  As proved in lecture, for quaternion $k$-algebras $H$, the involution given by conjugation is standard.
The \emph{degree} $\deg(H)$ of a $k$-algebra $H$ is the least positive integer $m$ such that every $\alpha\in H$ is the root of a monic polynomial in $k[x]$ of degree $m$, or $\infty$ if no such $m$ exists.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{4}
\item Show that a $k$-algebra $H$ with a standard involution satisfies $\deg(H)\le 2$.
Conclude that the $k$-algebra ${\rm M}_n(k)$ has a standard involution if and only if $n\le 2$.
\item Show that every commutative $k$-algebra of $k$-dimension 2 has a unique standard involution, and that in general, if a $k$-algebra has a standard involution, it is unique.
\item Let $H$ be a division $k$-algebra.  Show that $\deg(H)\le 2$ if and only if (i) $H=k$, (ii) $H$ is a quadratic field extension of $k$, or (iii) $H$ is a division quaternion algebra.
Conclude that $\deg(H)\le 2$ if and only if $H$ has a standard involution.

\item Show that for a division $k$-algebra $H$, the following are equivalent: (i) $H$ is a quaternion algebra, (ii) $H$ is noncommutative and $\deg(H)=2$, (iii) $H$ is central and $\deg(H)=2$.
\end{enumerate}

\noindent

\subsection*{Problem 6. Survey (2 points)}

Complete the following survey by rating each of the problems you attempted on a scale of 1 to~10 according to how interesting you found the problem (1 = ``mind-numbing," 10 = ``mind-blowing"), and how hard you found the problem (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
\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
10/19 & Elliptic curve primality proving & & & & \\\hline 
10/24 & Endomorphism algebras & & & & \\\hline 
10/26 & Ordinary/supersingular curves & & & & \\\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.

\end{document}