\newif\ifOCW
%\OCWtrue
\documentclass[11pt]{article}
\usepackage{amsmath,amssymb}
\usepackage{hyperref}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{hyperref}
\usepackage{enumerate}
\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{listings}
\usepackage{courier}
\usepackage{color}
\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{\FF}{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\End}{{\rm End}}
\newcommand{\M}{\textsf{M}}
\newcommand{\Gal}{{\rm Gal}}
\newcommand{\GL}{{\rm GL}}
\newcommand{\Frob}{{\rm Frob}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\lcm}{{\rm lcm}}
\newcommand{\kbar}{\bar{k}}

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

\noindent
These problems are related to Lectures 4--6.  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 sums to 100 points.
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 problems with others, but your writing must be your own.

\subsection*{Problem 1. V\'elu's formulas (14 points)}
Let $E_1/\Q$ be the elliptic curve  $y^2=x^3-21x+47$.  Show that $E_1$ admits a rational isogeny $\phi\colon E_1\to E_2$ of degree 3 whose kernel is generated by the point $(1,3\sqrt{3})$ and use V\'elu's formulas to compute an explicit equation for $E_2/\Q$ and an explicit rational map for the isogeny $\phi(x,y)=\left(\frac{u(x)}{v(x)},\frac{s(x)}{t(x)}y\right)$ in standard form.  Then compute $\phi(P)$, where~$P$ is the rational point $(-2,9)$ on $E_1$ and verify that $\phi(P)$ is a rational point on~$E_2$.

\subsection*{Problem 2. The torsion subgroup of $E(\Q)$ (85 points)}

Let $E$ be an elliptic curve over $\Q$.
The problem of determining the rational points on~$E$ is a famously hard problem that is still unsolved.
However, determining the rational points of finite order is easy.
In this problem you will design (but need not implement) an efficient algorithm for doing so.

We shall assume that $E$ is defined by a Weierstrass equation $y^2=x^3+Ax+B$, where $A$ and $B$ are \emph{integers}.
This assumption is not restrictive: we can always pick $u\in\Z$ so that the isomorphic curve $y^2=x^3+u^4Ax+u^6B$ has integer coefficients.

Let $P=(x_1,y_1)$ be a point of finite order $m>0$ in $E(\Q)$.
Our first goal is to prove that~$P$ must have integer coordinates.
This was proved independently first by Nagell \cite{nagell} and then by Lutz \cite{lutz} in the 1930's and is the first half of the Nagell-Lutz Theorem.
The standard proof \cite[\S 8.1]{washington} relies on a $p$-adic filtration, but in this problem you will give a shorter and simpler proof that relies only on properties of the division polynomials.
As shown in lecture, for any integer $n$ not divisible by $m$, the $x$-coordinate $x_n$ of the point $nP=(x_n,y_n)$ is given by $x_n=\phi_n(x_1)/\psi_n^2(x_1)$ where
\begin{align*}
\phi_n(x) &= x^{n^2} + \cdots,\\
\psi_n^2(x) &= n^2x^{n^2-1} + \cdots,
\end{align*}
with each ellipsis denoting lower order terms; see Problem 4 for the full definition of $\phi_n$ and~$\psi_n$, which depend on the curve coefficients $A$ and $B$.
\begin{enumerate}[{\bf (a)}]
\item Prove that for any positive integer $n<m$, if $x_n$ is an integer, then $x_1$ must be an integer.  Use this to reduce to the case that $m$ is prime.
\item Prove that if $m=2$ then $P$ has integer coordinates.
\item If $m$ is an odd prime then $x_1$ is a root of $\psi_m(x)=mx^{(m^2-1)/2}+\cdots\in \Z[x]$.  Using this, prove that $x_1$ is an integer, and then show that $y_1$ must also be an integer (thus~$P$ has integer coordinates as claimed).
\end{enumerate}

\noindent
We now need a few facts about the image of the torsion subgroup under reduction modulo a prime $p$ of good reduction for $E$.
So let $\Delta(E):=-16(4A^3+27B^2)$ be the discriminant of~$E$, and let $p$ be a prime that does not divide $\Delta$.
Reducing the coefficients $A$ and $B$ modulo $p$ then gives an elliptic curve $E_p/\Fp$.
Since we know that torsion points in $E(\Q)$ have integer coordinates, we can always reduce the coordinates of such a point modulo~$p$ to get the coordinates of a point in $E_p(\Fp)$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{3}
\item Prove that if $P\in E(\Q)$ has order $m$, then its reduction in $E_p(\Fp)$ has order $m$.
Deduce that the reduction map from $E(\Q)$ to $E_p(\Fp)$ is injective at torsion points.
\end{enumerate}

We now recall Mazur's theorem from Lecture 1, which tells us that the order of a torsion point in $E(\Q)$ can be at most $12$ (and cannot be $11$).  Our strategy is to pick a prime $p \ge 11$ of good reduction for $E$, find all the points of order less than or equal to $12$ in $E_p(\Fp)$, and then use the algorithm from Problem 5 of Problem Set 2 to try and lift these points to $E(\Q)$.
As proved in part (d) of that problem, given a polynomial $f\in \Z[x]$ and root $x_0$ of $f$ modulo $p$ that is not also a root of $f'$ modulo $p$, we can use Hensel's method to find a root $r\in\Z$ satisfying $r\equiv x_0\bmod p$ or prove that no such $r$ exists in $O(d\M(\log B))$ time; here $d=\deg f$ and $B$ is a bound on the absolute values of its coefficients.

The first step is to find a prime $p$ that does not divide the discriminant $\Delta$.
Doing this by trial division is not fast enough to give a quasi-linear running time, so we need to be a bit more clever.
We will instead use an algorithm for fast simultaneous modular reduction \cite[Alg.\,10.16]{gg}. to compute $\Delta \bmod p_i$ for the first several primes $p_1,\cdots, p_k$ greater than $11$, where $k$ is chosen so that $M=p_1\cdots p_k>\Delta$ (so we know that $\Delta\bmod p_i$ is nonzero for some $p_i$, we'll just pick the least one).

This is accomplished using a \emph{product tree}, a binary tree of integers whose bottom level (the leaves of the tree) consists of the primes $p_i$; for the sake of simplicity let us assume we round $k$ up to a power of $2$ so that we have a complete binary tree.
Working our way up from the leaves, we set the value of each internal node to the product of its children; eventually we reach the root of the tree, which then has the value $M=p_1\cdots p_k$.
We then replace the root $M$ with $d=|\Delta|\bmod M$, and for each of its children $m_1$ and $m_2$ we replace $m_i$ with $d_i=d\bmod m_i$ (which is $|\Delta|\bmod m_i$).
Recursively working our way down the tree, we eventually get $|\Delta|\bmod p_i$ in the leaves.

In order to bound the complexity of our algorithm, we define
\[
n:=\lg|A|+\lg|B|,
\]
which represents the bit-size of the input, the elliptic curve $E/\Q$ given as $y^2=x^3+Ax+B$ with $A,B\in\Z$.
Note that we then also have $\log |\Delta| = O(n)$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{4}
\item Prove that we can determine the least prime $p\ge 11$ that does not divide $\Delta$ in time $O(\M(n)\log n)$, and use the Prime Number Theorem to show that $p=O(n)$.
Feel free to use our usual assumption that $\M(n)$ grows super-linearly ($a\M(b)\le \M(ab)$).
\end{enumerate}

For each integer $m>1$, define the polynomial $f_m\in\Z[x]$ as follows:
\[
f_m(x) = \begin{cases}
x^3+Ax+B\qquad&\text{if $m=2$},\\
\psi_m/\psi_2 &\text{if $m>2$ is even},\\
\psi_m & \text{if $m$ is odd},
\end{cases}
\]
where $\psi_m$ denotes the $m$th division polynomial of  the elliptic curve $E\colon y^2=x^3+Ax+B$.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{5}
\item Prove that if $P=(x_1,y_1)\in E(\Q)$ has finite order $m$ not divisible by $p$ then we have $f_m(x_1)=0\bmod p$ and $f_m'(x_1)\ne 0\bmod p$.
\end{enumerate}

It follows that their exist suitable starting values $x_0$ and $z_0$ to which we can apply the integer root-finding algorithm from Problem Set 2 (see Problem 5) to obtain an integer root of $f_m(x)$ that is congruent to $x_0$ modulo $p$.
By part (c), this root must be equal to $x_1$.
This still leaves the question of how to find such an $x_0$.
We know it must appear as the $x$-coordinate of some point in $E_p(\Fp)$ of order $m$, so it suffices to find all such points for all the values of $m\le 12$ permitted by Mazur's theorem.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{6}
\item Give an algorithm to enumerate all points $(x_0,y_0)\in E_p(\Fp)$ in time $O(n\M(\log n))$.

\item Give an algorithm to construct the set $S$ consisting of all points in $E_p(\Fp)$ of order at most 12 in time $O(n\M(\log n))$, and prove that the cardinality of $S$ is $O(1)$ (meaning it is bounded by a constant that does not depend on $n$).

\item Prove that there is a bound $H>0$ with $\log H=O(n)$ such that the coefficients of $f_m$ all have absolute value bounded by $H$, for $2\le m\le 12$.
You don't need to give an explicit value for $H$, just show that it exists and can be effectively computed.

\item Using the $O(d\M(\log H))$ complexity bound of the integer root-finding-over algorithm (proved in part (d) of Problem 5 on Problem Set 2), show that for any point $Q\in S$ of order $m$ you can either find a point $P\in E(\Q)$ of order $m$ that reduces to $Q$ modulo $p$, or prove that no such $P$ exists\footnote{Note that not every point $Q\in S$ is necessarily the reduction of a point $P\in E(\Q)$.} in time $O(\M(n))$.

\item Conclude that you can enumerate the torsion points in $E(\Q)$ in $O(\M(n)\log n)$ time.
\end{enumerate}

It is worth noting that the algorithm you have just designed is asymptotically faster than both of the algorithms given in \cite{washington}: one is based on the Lutz--Nagell Theorem \cite[Thm.\ 8.7]{washington}, which requires factoring $\Delta$ and is not polynomial time, and the other uses Doud's algorithm~\cite{doud} which is quasi-quadratic but not quasi-linear.\footnote{Doud gives a quasi-cubic bound in \cite{doud} but using FFT-based multiplication makes it quasi-quadratic.}  But also see~\cite{gsot}, which describes three algorithms, the two given in \cite{washington} and a third using division polynomials that is similar to the algorithm above (their complexity bound is not as sharp).

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{11}
\item Now suppose we would like an algorithm that does not depend on Mazur's result.  Explain how to modify the algorithm above to replace $12$ with an alternative bound (which may depend on $E$), and analyze the complexity of the resulting algorithm.
\end{enumerate}

\subsection*{Problem 3. Computing division polynomials (85 points)}
For integers $m\ge 0$, define $\psi_n\in\Z[x,y,A,B]$ by
\begin{align*}
\psi_0 &= 0,\\
\psi_1 &= 1,\\
\psi_2 &= 2y,\\
\psi_3 &= 3x^4+6Ax^2+12Bx-A^2,\\
\psi_4 &= 4y(x^6+5Ax^4+20Bx^3-5A^2x^2-4ABx-8B^2-A^3),\\
\psi_{2m}&=\frac{1}{2y}\psi_m(\psi_{m+2}\psi_{m-1}^2-\psi_{m-2}\psi_{m+1}^2)\qquad(m\ge 3),\\
\psi_{2m+1}&=\psi_{m+2}\psi_m^3-\psi_{m-1}\psi_{m+1}^3 \hspace{70pt}(m\ge 2).
\end{align*}
Let $\phi_1=x$ and $\omega_1=y$, and for integers $n>1$ define
\begin{align*}
\phi_m &=x\psi_m^2-\psi_{m+1}\psi_{m-1},\\
\omega_m &=\frac{1}{4y}(\psi_{m+2}\psi_{m-1}^2-\psi_{m-2}\psi_{m+1}^2).
\end{align*}
 It is a straight-forward exercise (which you are not required to do) to show that these polynomials have the form
\begin{align*}
\phi_m(x) &= x^{m^2} +\  \cdots,\\
\omega_n(x,y) &=
\begin{cases}
y(x^{3(m^2-1)/2} +\  \cdots)\qquad &m \text{ odd},\\
x^{3m^2/2} +\  \cdots\qquad&m \text { even},\\
\end{cases}\\
\psi_m(x,y) &=
\begin{cases}
nx^{(m^2-1)/2} +\  \cdots\qquad&m \text{ odd},\\
y(nx^{(m^2-4)/2} +\  \cdots)\qquad &m \text { even},\\
\end{cases}
\end{align*}
where each ellipsis denotes terms of lower degree in $x$.
\bigskip

\noindent
In practical applications it is more convenient to work with the univariate polynomials
\[
f_m(x) = \begin{cases}
\psi_m\qquad&m \text{ odd},\\
\psi_m/\psi_2&m \text{ even}.\\
\end{cases}
\]
Note that $\psi_2=2y$, and it follows from the formulas above that $f_m$ does not depend on~$y$.  If $P=(x_0,y_0)$ is
a point on the elliptic curve $y^2=x^3+Ax+B$ with $y_0\ne 0$ (so $P$ is not a 2-torsion point), then $f_m(x_0)=0$ if and only if $mP=0$.
In this problem you will develop an algorithm to compute $f_m$ without needing to compute $f_k$ for all $k\le m$.

\begin{enumerate}[{\bf (a)}]
\item Let $F(x)=4(x^3+Ax+B)$.  Using the recursion formulas for $\psi_{2m}$ and $\psi_{2m+1}$, derive recursion formulas for $f_{2m}$ and $f_{2m+1}$ that involve $f_{m-2},\ldots,f_{m+2}$ and $F$.  Note that you may need to distinguish the cases where $m$ is odd and even.
\item Show that there exist positive integers $a,b$ such that for all $k\ge a$ if you are given $f_{k-a},\ldots,f_{k+b}$ and $F$, you can use the recurrences in \textbf{(a)} to compute the polynomials
$f_{2k-a},\ldots,f_{2k+b}$ (call this \emph{doubling}), and also the polynomials $f_{2k+1-a},\ldots,f_{2k+1+b}$ (call this \emph{doubling-and-adding}).  Determine the smallest values of $a$ and $b$ that work.
\item Implement an algorithm that, given $m\in\Z_{\ge 1}$, an odd prime $p$, and coefficients $A,B$ with $p\!\nmid\!(4A^3+27B^2)$, computes the division polynomial $f_m\in\Fp[x]$ for the elliptic curve $E/\Fp$ defined by $y^2=x^3+Ax+B$, using a left-to-right binary exponentiation approach.
Here are a few tips (but feel free to use any design you like):
\begin{itemize}
\item
Work in the polynomial ring $\Fp[x]$, which you can create in Sage by typing \texttt{R.<x>=PolynomialRing(GF(p))}.
Note that $A$ and $B$ are now elements of $\Fp$, not variables.  Precompute $F=4(x^3+Ax+B)\in\Fp[x]$.
\item 
You need an initial vector of division polynomials $[f_{k-a},\ldots,f_{k+b}]$ to get started, but you have the freedom to choose exactly which $k\ge a$ to use. Depending on the binary representation of $m$ it may be more convenient to start with $k=a+1$ or $k=a+2$ rather than $k=a$.
\item
To test your code, you can compare results with Sage, which already knows how to compute $f_m$, via
\begin{lstlisting}
FF=GF(p); R.<x>=PolynomialRing(FF)
E=EllipticCurve([FF(A),FF(B)])
E.division_polynomial(n,x,0)
\end{lstlisting}
\textbf{Important}: you must include the ``$0$'' in the call to \texttt{division\_polynomial} in order to get polynomials that match $f_m$.
\item
Your program should be quite fast, but be careful not to test it with values of $m$ that are too large --- the degree of $f_m$ is quadratic in $m$, so if $m$ is, say, a million, you would need several terabytes of memory to store $f_m$.
\end{itemize}
\item Analyze the time and space complexity of your algorithm as a function of $m$ and $n=\log p$ and give an upper bound on the size of its output.

\item Suppose you replace $\Fp$ with $\Z$ in your algorithm (so now $A,B\in \Z$ and you work in $\Z[x]$).  Analyze the time and space complexity of your algorithm as a function of $m$ and $n=\log(|A|+|B|)$ and give an upper bound on the size of its output.

\item
Modify your program so that it performs its computations modulo $x^7$ (to compute $f(x)\bmod x^7$ in Sage use \texttt{f.mod(x\^{}7)}).
Now let $A$ be the least prime greater than the last two digits of your student ID, let $B$ be the least prime greater than the first two digits of your student ID, and let $p=65537$.  Let $E/\Fp$ be the elliptic curve defined by $y^2=x^3+Ax+B$, and let $m=N^{100}+1$, where $N$ is the integer formed by adding the last three digits of your student ID to 9000.
\begin{enumerate}[{\bf (i)}]
\item
Use your modified program to compute $f_m\bmod x^7$ and record the result in your problem set.
Be sure to first test your program with smaller values of $m$ and verify the results with Sage as shown above (your answer to this question will be heavily weighted when grading this problem, so please be careful).
\item
Time your program using the \texttt{\%timeit} line magic.  How long does it take?
\end{enumerate}
\end{enumerate}

\subsection*{Problem 4. Galois actions and $\ell$-isogenies (85 points)}
Let $k$ be a perfect field (so every extension of $k$ is separable; this holds when $\mathrm{char}(k)=0$ or $k$ is a finite field, for example), fix an algebraic closure $\kbar$, and let $E/k$ be an elliptic curve.  For each $n\ge 0$ the field $k(E[n])$ obtained by adjoining the coordinates of every point in the $n$-torsion subgroup $E[n]:=\{P\in E(\kbar):nP=0\}$ is the \emph{$n$-torsion field} of $E$.
For any point $P=(x:y:z)\in E(\kbar)$ and automorphism $\sigma\in\Gal(\kbar/k)$ let $\sigma(P):=(\sigma(x):\sigma(y):\sigma(z))$.

\begin{enumerate}[{\bf (a)}]
\item Show that for any $P\in E(\kbar)$ and $\sigma\in \Gal(\kbar/k)$ we have $\sigma(P)\in E(\kbar)$, and  that for all $P,Q\in E(\kbar)$ we have $\sigma(P+Q)=\sigma(P)+\sigma(Q)$.
Conclude that the map $P\mapsto \sigma(P)$ defines a group action of $\Gal(\kbar/k)$ on $E(\kbar)$ that commutes with addition, and that each $\sigma\in \Gal(\kbar/k)$ thus induces an automorphism of the group $E(\kbar)$.
\item Show that the action of $\Gal(\kbar/k)$ on $E(\kbar)$ restricts to an action on $E[n]$.  Conclude that $k(E[n])$ is a Galois extension of $k$.
\item Give an explicit example of an elliptic curve $E/k$ and a finite subgroup $G\subseteq E(\kbar)$ for which the action of $\Gal(\kbar/k)$ in $E(\kbar)$ does \emph{not} restrict to an action on $G$; that is, exhibit a point $P\in G$ and an automorphism $\sigma\in\Gal(\kbar/k)$ for which $\sigma(P)\not\in G$.
Now give an example (possibly the same one) where the field extension of $k$ obtained by adjoining the coordinates of every point $P\in G$ is not even a Galois extension.
\item Show that for any finite subgroup $G$ of $E(\kbar)$ there is a separable isogeny $\phi\colon E\to E'$ defined over $k$ with kernel $G$ if and only if $G$ is \emph{Galois stable}, meaning that $\sigma(P)\in G$ for all $P\in G$ and $\sigma\in \Gal(\kbar/k)$, and that in this case the field $k(\ker \phi)$ obtained by adjoining the coordinates of every point $P\in \ker\phi$  to $k$ is a Galois extension of $k$.
\end{enumerate}

\noindent
Let $\ell$ be an odd prime different from the characteristic of $k$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{4}
\item Show that $\Aut(E[\ell])\simeq \GL_2(\Fl)$, and that the action of $\Gal(\kbar/k)$ on $E[\ell]$ induces an injective group homomorphism $\rho_\ell\colon \Gal(k(E[\ell])/k)\to \GL_2(\Fl)$.
Use this to show that the degree of the field extension $k(E[\ell])/k$ is less than $\ell^4$.
\item Show that when $k$ is a finite field the degree of $k(E[\ell])/k$ is actually less than $\ell^2$.
\end{enumerate}

The isomorphism you proved in (e) is not unique; for the sake of concreteness, let us view $\GL_2(\Fl)$ as acting on column vectors by multiplication on the left.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{6}
\item The $\ell$-division $\psi_\ell(x)$ of $E$ has degree $(\ell^2-1)/2$ (see Problem 4).
Its splitting field $L$ is necessarily a subfield of the $\ell$-torsion field $k(E[\ell])$.
Show that $[k(E[\ell])\!:\!L]\le 2$ with equality if and only if the image of $\rho_\ell$ contains $-I\in \GL_2(\Fl)$.
\end{enumerate}
We say that $E$ \emph{admits a rational $\ell$-isogeny} if there exists an isogeny $\phi\colon E\to E'$ of degree $\ell$ that is defined over $k$.  
\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{7}
\item Show that whenever $E$ admits a rational $\ell$-isogeny the $\ell$-division polynomial $\psi_\ell(x)$ has a factor of degree $(\ell-1)/2$ (see \textbf{(l)} for the converse).  Show that if $\phi\colon E\to E'$ is a rational $\ell$-isogeny then the field extension $k(\ker\phi)/k$ has degree less than $\ell$.
\item Show that $E$ admits a rational $\ell$-isogeny if and only if the image $G_\ell$ of $\Gal(k(E[\ell])/k)$ in $\GL_2(\Fl)$ fixes a linear subspace of $\Fl^2$, in which case $G_\ell$ is conjugate to a subgroup of upper triangular matrices in $\GL_2(\Fl)$ and the degree of $k(E[\ell])/k$ is less than $\ell^3$.
\item Show that $E$ has a rational point of order $\ell$ if and only if $G_\ell$ is conjugate to a subgroup of matrices $\left(\begin{smallmatrix}1&*\\0&*\end{smallmatrix}\right)$, in which case the degree of $k(E[\ell])/k$ is less than~$\ell^2$.
\item Let $m$ be the number of rational $\ell$-isogenies admitted by $E$ that have distinct kernels.  Show that $m\in \{0,1,2,\ell+1\}$, with $m\ge 2$ if and only if $G_\ell$ is conjugate to a subgroup of diagonal matrices in $\GL_2(\Fl)$, and $m=\ell+1$ if and only if $G_\ell$ is conjugate to a subgroup of scalar matrices in $\GL_2(\Fl)$.
\item \textbf{Optional}: Show that the converse to the first part of \textbf{(h)} need not hold by exhibiting an elliptic curve $E$ and a prime $\ell$ for which the $\psi_\ell(x)$ has a factor of degree $(\ell-1)/2$ but $E$ does not admit a rational isogeny of degree $\ell$.  (hint: you won't find counterexamples over finite fields or over $\Q$, but you can over number fields).
\end{enumerate}

\subsection*{Problem 5. Survey (1 point)}
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 difficult you found the problem (1 = ``trivial," 10 = ``brutal").  Also estimate the time you spent on each problem to the nearest half hour.

\begin{center}
\begin{tabular}{l|r|r|r|}
& Interest & Difficulty & Time Spent\\\hline
Problem 1 & & & \\\hline
Problem 2 & & & \\\hline
Problem 3 & & & \\\hline
Problem 4 & & & \\\hline
\end{tabular}
\end{center}
Feel free to record any additional comments you have on the problem sets or lectures, and in particular, ways in which you think they could be improved.
\medskip

\noindent
\textbf{Collaborators/sources}:

\begin{thebibliography}{9}
\bibitem{doud} D. Doud, \href{http://link.springer.com/article/10.1007/BF02678043}{\textit{A procedure to calculate torsion of elliptic curves over $\Q$}}, Manuscripta Mathematica \textbf{95} (1998), 463--469.
\bibitem{gsot} I. Garc\'ia-Selfa, M.A. Olalla, and J.M. Tornero, \href{https://www.sciencedirect.com/science/article/pii/S0022314X02927800}{\textit{Computing the rational torsion of an elliptic curve using Tate normal forms}}, J. Number Theory \textbf{96} (2002), 76--88.
\bibitem{gg} J. von zur Gathen and J. Gerhard, \href{https://www.cambridge.org/core/books/modern-computer-algebra/DB3563D4013401734851CF683D2F03F0}{\textit{Modern Computer Algebra}}, third edition, Cambridge University Press, 2013.
\bibitem{lutz} E. Lutz, \href{http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN243919689_0177&DMDID=DMDLOG_0024}{\textit{Sur l'equation $y^2=x^3-ax-b$ dans les corps $p$-adic}}, J. Reine Angew. Math. \textbf{177} (1937), 237--247.
\bibitem{nagell} T. Nagell, \textit{Solution de quelque probl\`{e}mes dans la th\'{e}orie arithm\'{e}tique des cubiques planes du premier genre}, Wid. Akad. Skrifter Oslo I \textbf{1} (1935).
\bibitem{silverman} J.H. Silverman, \href{https://link.springer.com/book/10.1007/978-0-387-09494-6}{\textit{The arithmetic of elliptic curves}}, second edition, Springer, 2009.
\bibitem{washington}
     L.C. Washington, \href{https://doi.org/10.1201/9781420071474}{\textit{Elliptic curves: Number theory and cryptography}}, 2nd edition, CRC press, 2008.
\end{thebibliography}
\end{document}