\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{hyperref}
\hypersetup{colorlinks=true,urlcolor=RawSienna,citecolor=RoyalPurple,linkcolor=MidnightBlue}
\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{\Fptwo}{\mathbb{F}_{p^2}}
\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{\smat}[4]{\footnotesize{$\begin{pmatrix}#1&#2\\#3&#4\end{pmatrix}$}}

\newcommand{\DL}{{\rm DL}^*}

\theoremstyle{definition}
\newtheorem*{definition*}{Definition}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.783 Elliptic Curves\hspace{220pt}Spring~2015}\\\vspace{4pt}
\textbf{Problem Set \#5\hspace{222pt}Due: 03/13/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 9-10.
As usual, the first person to spot each non-trivial typo/error will receive one point of extra credit.
\medskip

\noindent\textbf{Instructions}: Solve \textbf{two} of Problems 1-3 and then do Problem~4, which is a survey.  Please be sure to include your name on your solutions and give your submission a filename of the form \texttt{LastNamePSet5.pdf}.

\subsection*{Problem 1.  The image of Galois (50 points)}
Let $E/\Q$ be an elliptic curve, let $\ell$ be a prime, and let $K=\Q(E[\ell])$ be the Galois extension of~$\Q$ obtained by adjoining the coordinates of all the points in the $\ell$-torsion subgroup $E[\ell]$ to $\Q$.
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,
\]
thus there is a group homomorphism
\[
\rho_E:\Gal(K/\Q)\to \GL_2(\Fl)
\]
that maps each field automorphism $\sigma\in\Gal(K/\Q)$ to an element of the general linear group $\GL_2(\Fl)$, which we may view as an invertible $2\times 2$ matrix with coefficients in $\Fl$ (after choosing a basis for $E[\ell]$).

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$ is a representation of the group $\Gal(K/\Q)$, known as the \emph{mod-$\ell$ Galois representation} attached to $E$.\footnote{One can replace $K$ with any algebraic extension (including an algebraic closure of $\Q$.}

For each prime $p\ne\ell$ where $E$ has good reduction there is a \emph{Frobenius element} $\Frob_p$ of $\Gal(K/\Q)$, which reduces to the Frobenius map $x\mapsto x^p$ modulo a prime of $K$ lying above $p$.
Let $E_p$ denote the reduction of $E$ modulo such a prime $p$.
The Frobenius element is mapped by $\rho_E$ to an element of $\GL_2(\Fl)$ corresponding to $\pi_\ell$, the restriction of the Frobenius endomorphism of $E_p$ to the $\ell$-torsion subgroup $E_p[\ell]$.
The \emph{Frobenius element} $\Frob_p$ is only determined up to conjugacy (and is usually identified with its conjugacy class), since it depends on a choice of basis, but we can unambiguously determine the characteristic polynomial of $\rho_E(\Frob_p)=\pi_\ell$.
In particular, the trace of $\rho_E(\Frob_p)$ is the trace of Frobenius $t=p+1-\#E_p(\Fp)$ modulo $\ell$, and the determinant of $\rho_E(\Frob_p)$ is simply $p\bmod \ell$ (note that $p\ne \ell$).

The Chebotarev density theorem tells us that for any conjugacy class $C$ of $\Gal(K/\Q)$, the proportion of primes $p$ for which $\Frob_p$ lies in $C$ is exactly the ratio $\#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$ to a uniformly random element of the image of $\rho_E$ in $\GL_2(\Fl)$.
For a typical elliptic curve $E/\Q$, the representation $\rho_E$ 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$ 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.

The purpose of this exercise is for you to attempt to determine the image of $\rho_E$ 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)$.
Not every subgroup of $\GL_2(\Fl)$ can arise as the image of $\rho_E$, since, for example, $\im \rho_E$ must contain matrices with ever possible nonzero determinant (as $p$ varies, $\det\pi_\ell$ will eventually hit every element of $\Fl^*$).

For $\ell=3$ there are, up to conjugacy, 8 candidate subgroups $G$ of $\GL_2(\Fl)$ for the image of~$\rho_E$.
These are listed in Table 1, and can also be found in this \href{https://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783%20Problem%20Set%205%20Problem%202.sagews}{Sage worksheet}.

\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$& 4 & dihedral & \smat{2}{0}{0}{1}, \smat{2}{0}{0}{2}\\\vspace{2pt}
$D_3=S_3$& 6 & dihedral & \smat{2}{1}{2}{0}, \smat{1}{0}{1}{2}\\\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$ in $\GL_2(\FF_3)$.
\end{center}

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

Thus 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])$.

\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 9 (which can be found in this \href{https://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783 Lecture 9- Schoof's algorithm.sagews}{Sage workhseet}) 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 (a) 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$ and for which $E$ has good reduction,
and for each $E_p$, computes the triple $(\det \pi_\ell, \tr \pi_\ell, |\pi_\ell|)$.
In Sage you can use \texttt{prime\_range(N+1)} to 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://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783%20Problem%20Set%205%20Problem%202.sagews}{Sage worksheet}
Then normalize the counts by dividing by the number of primes $p$ used, yielding a ratio for each triple.

For $\ell=3$, use your program to provisionally determine the image of $\rho_E$ 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 this \href{https://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783%20Problem%20Set%205%20Problem%202.sagews}{Sage worksheet}.

\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+4752x+127872$\\
 $y^2=x^3+5805x-285714\qquad\qquad$&$y^2=x^3+652509x-621544482$\\
\end{tabular}
\end{center}

\item
Note that if a given triple $(\det \pi_\ell, \tr \pi_\ell, |pi_\ell|)$ occurs for some $E_p$ but does not occur in a candidate subgroup $G\subset\GL(\Fl)$,  you can immediately rule out $G$ as a possibility for the image of $\rho_E$.
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$ is surjective for $\ell=3$.

Use this to devise an algorithm that attempts to prove $\rho_E$ is surjective for $\ell=3$.
Your algorithm should return \texttt{true} as soon as it can determine $\im\rho_E=\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 each $\pi_\ell$ is uniformly and independently distributed over the image of $\rho_E$ as $p$ varies.
If your program returns \texttt{true}, then $\rho_E$ is definitely surjective; if it returns \texttt{false} it is almost certainly not surjective, but there is a small probability of error.

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(A^3+27B^2)=0$, use your program to test whether the mod-3 Galois representation $\rho_E$ is surjective or not.  List five curves for which your program returns \texttt{false}, and provisionally identify the image of $\rho_E$ in each such case as in part 3 above (you may need to test a few thousand curves to achieve this).
\end{enumerate}

\subsection*{Problem 2.  Schoof's algorithm (50 points)}
In this problem you will analyze the complexity of Schoof's algorithm, as described in \href{http://math.mit.edu/classes/18.783/LectureNotes9.pdf}{Lecture 9} (Algorithms 9.1 and 9.3) and implemented in this \href{https://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783%20Lecture%209-%20Schoof's%20algorithm.sagews}{Sage worksheet}.
In your complexity bounds, use $\M(m)$ to denote the complexity of multiplying two $m$-bit integers.
You may wish to recall that the complexity of multiplying polynomials in $\Fp[x]$ of degree~$d$ is $O(\M(d\log p))$, provided that $\log d = O(\log p)$ (in Schoof's algorithm, $\ell=O(\log p)$, so this certainly applies).
Under the same assumption, the complexity of inverting a polynomial of degree $O(d)$ modulo a polynomial of degree $d$ is $O(\M(d\log p)\log d)$.

\begin{enumerate}[{\bf (a)}]
\item Analyze the time complexity of computing $t_\ell$ as described in Algorithm 9.3 of the lecture notes and implemented in the \texttt{trace\_mod} function in the worksheet.
Give separate bounds for each of the four non-trivial steps in Algorithm 9.3 as well as overall bounds for the entire algorithm.
Express your bounds in terms of $\ell$ and $n=\log p$, using $\M(m)$ to denote the cost of multiplying two $m$-bit integers.

\item Analyze the total time complexity of Schoof's algorithm, as described in Algorithm~9.1 of the lectures notes and implemented in the \texttt{Schoof} function of this \href{https://cloud.sagemath.com/projects/de378c46-9f0f-42bb-9f95-0d1b0073e8e9/files/18.783%20Lecture%209-%20Schoof's%20algorithm.sagews}{Sage worksheet},
as a function of $n=\log p$.
Give your answer in three forms, first using $\M(m)$ to express the cost of multiplying $m$-bit integers, then after plugging in the na\"ive bound $\M(m)=O(m^2)$ or the Sch\"onhage-Strassen bound for FFT-based multiplication $\M(m)=O(m\log m\log\log m)$.

\item In your answer to part (a), you should have found that the time complexity bound for one particular step is strictly worse than any of the other steps of Algorithm~9.3.
Explain how to modify Algorithm~9.3 so that this step no longer strictly dominates the asymptotic running time.

\item Revise your time and space complexity estimates in part (b) to reflect part (c).

\item Analyze the space complexity of Schoof's algorithm as a function of $n$, both before and after your optimization in part (c).
\end{enumerate}


\subsection*{Problem 3. A Las Vegas algorithm to compute $E(\Fp)$. (50 points)}

Let $E/\Fp$ be an elliptic curve over a finite field $\Fp$ of prime order $p$.
In this problem you will use the extended discrete logarithm to design (but need not implement) a Las Vegas algorithm to determine the structure of $E(\Fp)$ as a sum of two cyclic groups
\[
E(\Fp)\simeq \Z/N_1\Z\oplus\Z/N_2\Z,
\]
with $N_1|N_2$.
We will assume that the group order $N$ has already been computed, either by Schoof's algorithm or by the Las Vegas algorithm from Problem Set~3.

Our strategy is to determine the structure of the $\ell$-Sylow subgroups of $E(\Fp)$ for each prime $\ell$ dividing $N$.
Recall that an $\ell$-Sylow subgroup is a maximal $\ell$-group (a group in which the order of every element is a power of $\ell$), and in an abelian group, there is a just one $\ell$-Sylow subgroup and it contains every element whose order is a power of $\ell$.
If $\ell$ divides $N$ but $\ell^2$ does not, then the $\ell$-Sylow subgroup is obviously isomorphic to $\Z/\ell\Z$, so we only need to consider primes whose square divides~$N$.
Furthermore, even if $\ell^2$ does divide $N$, unless $\ell$ divides $p-1$, the $\ell$-Sylow subgroup will still be cyclic:
\begin{enumerate}[{\bf (a)}]
\item Prove that if the $\ell$-Sylow subgroup of $E(\Fp)$ is not cyclic then $p\equiv 1\bmod \ell$.
\end{enumerate}

\noindent
This yields the following high-level algorithm to compute $N_1$ and $N_2$, given $N$.
\begin{enumerate}
\item Compute the prime factorization $N$.
\item Set $N_1=1$ and $N_2=1$, and for each maximal prime power $\ell^e$ dividing $N$:
\begin{enumerate}
\item If $e=1$ or $\ell$ does not divide $p-1$, then set $N_2=\ell^eN_2$ and continue.
\item Otherwise, compute the structure $\Z/\ell^{e_1}\Z\oplus\Z/\ell^{e_2}\Z$ of the $\ell$-Sylow subgroup of $E(\Fp)$ as described below, with $e_1\le e_2$,
and set $N_1=\ell^{e_1}N_2$ and $N_2=\ell^{e_2}N_2$.
\end{enumerate}
\item Output $N_1$ and $N_2$
\end{enumerate}

All we need now is an algorithm to compute the $\ell$-Sylow subgroup $G_\ell$ of $E(\Fp)$, given the orders $\ell^e$ and $N$ of $G_\ell$ and $E(\Fp)$, respectively.
Our strategy is to first pick two random points $P_1,P_2\in G_\ell$, by generating random points in $E(\Fp)$ and multiplying them by $N/\ell^e$.  We hope that these points generate $G_\ell$.  Next, we reduce them to what we hope is a \emph{basis} for $G_\ell$, that is, points $Q_1$ and~$Q_2$ such that $G_\ell\simeq\langle Q_1\rangle\oplus\langle Q_2\rangle$.
We then have $G_\ell\simeq \Z/\ell^{e_1}\Z\oplus\Z/\ell^{e_2}\Z$ where $\ell^{e_1}=|Q_1|$, $\ell^{e_2}=|Q_2|$.
Note that we can quickly compute the order of any element of $G_\ell$, since it must be a power of $\ell$.
Provided that we know the points $Q_1$ and $Q_2$ are \emph{independent} (meaning that $\langle Q_1,Q_2\rangle\simeq\langle Q_1\rangle\oplus\langle Q_2\rangle$), in order to verify that we actually have computed a basis for~$G_\ell$ and not some proper subgroup, we just need to check that $e_1+e_2=e$.
If this does not hold, we try again with two new random points $P_1$ and $P_2$; eventually we must succeed. \medskip

Your job is to flesh out this strategy and analyze the resulting algorithm.
We first recall the definition of the extended discrete logarithm given in Lecture 9.
\begin{definition*}
For elements $\alpha$ and $\beta$ of a finite group $G$, the \emph{extended discrete logarithm} of~$\beta$ with respect to $\alpha$, denoted $\DL(\alpha,\beta)$, is the pair of positive integers $(x,y)$ with $\alpha^x=\beta^y$, where $y$ is minimal subject to $\beta^y\in\langle\alpha\rangle$, and $x=\log_\alpha\beta^y$; or in additive notation, $x\alpha=y\beta$ with $y$ minimal subject to $y\beta\in \langle \alpha\rangle$.
\end{definition*}

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{1}
\item Prove each of the following statements for a finite abelian $\ell$-group $G$ containing elements $\alpha$ and $\beta$.
\begin{enumerate}[(i)]
\item If $G$ has $\ell$-rank at most 2 and $\alpha$ and $\beta$ are random elements uniformly distributed over the elements of $G$, then the probability that $G=\langle \alpha,\beta\rangle$ is at least 3/8.
\item If $(x,y)=\DL(\alpha,\beta)$ then $y$ is a power of~$\ell$.

\item For $(x,y)=\DL(\alpha,\beta)$ the following are equivalent:
\begin{itemize}
\item $x=|\alpha|$ and $y=|\beta|$;
\item $\langle\alpha,\beta\rangle$ has order $|\alpha|\cdot|\beta|$.
\item $\alpha$ and $\beta$ are independent;
\end{itemize}
\item If $|\alpha|\ge|\beta|$ and $(x,y)=\DL(\alpha,\beta)$ then $y|x$ and $\gamma=\beta-(x/y)\alpha$ and $\alpha$ are independent.
\end{enumerate}
\end{enumerate}

The key fact is (iv), which tells us that we should order the $P_i$ so that $|P_1|\le |P_2|$ and then let $Q_1=P_1-(x/y)P_2$ and $Q_2=P_2$, where $(x,y)=\DL(P_2,P_1)$.  If we then compute $\ell^{e_1}=|Q_1|$ and $\ell^{e_2}=|Q_2|$, it follows from (iii) that $G_\ell=\langle Q_1,Q_2\rangle$ if and only if $e_1+e_2=e$.  Fact (i) tells that we expect this to occur within less than 3 iterations, on average.
By~(ii), we can compute $(x,y)=\DL(P_2,P_1)$, by attempting to compute $x=\log_{P_2}\ell^iP_1$ for $i=0,1,2,\ldots$ until we succeed, at which point we have $y=\ell^i$.\footnote{There are much better ways to do this (a binary search, for example), but using them won't improve the worst-case complexity of the overall algorithm.}

To compute $\log_{P_2}\ell^iP_1$, we use the prime-power case of the Pohlig-Hellman algorithm described in Lecture 10 to reduce the problem to a discrete logarithm computation in a group of prime order~$\ell$ for which we use the baby-steps giant-steps method.
\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{2}
\item Prove that in a cyclic group of prime-power order $N=\ell^e$ the complexity of the Pohlig-Hellman algorithm is
\[
O(e\log\ell\log e + e\sqrt{\ell})
\]
group operations.
Use this to bound the bit-complexity of computing $\log_{P_2}\ell^iP_1$ in the $\ell$-Sylow subgroup of $E(\Fp)$ with order $\ell^e$.
\item
Write down a high-level description (not a program) of an algorithm to compute the structure of the $\ell$-Sylow subgroup $G_\ell$ of $E(\Fp)$ in the form $\Z/\ell^{e_1}\Z\oplus\Z/\ell^{e_2}\Z$, given $N=\#E(\Fp)$ and $\ell^e=\#G_\ell$, and analyze its expected time complexity as a function of~$\ell$, $n=\log p$, and $e$.
\item
Analyze the total expected time complexity of the algorithm to compute the structure of $E(\Fp)$ in the form $\Z/N_1\Z\oplus\Z/N_2\Z$, given $N=\#E(\Fp)$ (hint: first figure out what the worst case is, then analyze that).
You can assume that we have a Las Vegas algorithm that factors $N$ in subexponential time, meaning it is faster than $N^\epsilon$ for any $\epsilon > 0$.
\end{enumerate}

\subsection*{Problem 4. Survey}

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 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
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
3/5 & Schoof's Algorithm & & & & \\\hline 
3/10 & Discrete Logarithm Problem & & & & \\\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}