To: NMBRTHRY@LISTSERV.NODAK.EDU
Date: Tue, 25 Sep 2001 13:37:18 -0400
We are pleased to announce a new record for the discrete logarithm
problem. We were able to compute discrete logarithms in
GF(2^521). This was done in one month on a unique 525MHz
quadri-processors Digital Alpha Server 8400 computer. The approach
that we followed is a careful implementation of the general Function
Field Sieve as described from a theoretical point of view by Adleman
[Ad94].
As far as we know, the largest such computation previously done was
performed in GF(2^401) [GoMc92] using an algorithm due to Coppersmith
[Co84].
[...]
So, as a conclusion, time that we need for computing discrete
logarithms in GF(2^521) on a 525 MHz quadri-processor alpha server
8400 computer is approximatively 12 hours for each, once the sieving
step (21 days) and the linear algebra step (10 days) is performed.
Antoine JOUX (DCSSI, Issy les Moulineaux, France, Antoine.Joux@ens.fr),
Reynald LERCIER (CELAR, Rennes, France, lercier@celar.fr).
\end{verbatim}
\section{Realistic Example}
\begin{verbatim}
? p=nextprime(93450983094850938450983409583)
%17 = 93450983094850938450983409611
? isprime((p-1)\2)
%18 = 0
? nextgoodprime(p) = while(!isprime((p-1)\2), p=nextprime(p+1)); p
? nextgoodprime(p)
%19 = 93450983094850938450983409623
? g=2
%21 = 2
? znorder(Mod(g,p))
%22 = 93450983094850938450983409610
? ?random
random({N=2^31}): random integer between 0 and N-1.
? nikita = random(p)
%23 = 18319922375531859171613379181
? michael = random(p)
%24 = 82335836243866695680141440300
? nikita_say = Mod(g,p)^nikita
%26 = Mod(17037287637415625385373411504, 93450983094850938450983409611)
? michael_say=Mod(g,p)^michael
%27 = Mod(2201425894324369970772940547, 93450983094850938450983409611)
? secret = nikita_say^michael
%28 = Mod(25591938014843312529239952955, 93450983094850938450983409611)
? secret = michael_say^nikita
%29 = Mod(25591938014843312529239952955, 93450983094850938450983409611)
\end{verbatim}
\chapter{The RSA Public-Key Cryptosystem, I}
\hd{Key Ideas:}
\begin{itemize}
\item Creating an RSA public key
\item Encrypting and decrypting messages
\item Breaking RSA and factoring
\end{itemize}
\tableofcontents
\section{How RSA works}
\subsection{One-way Functions}
The {\em fundamental idea} behind RSA is to try to construct
a ``one-way function'', i.e., an ``encryption'' function
$$
E : X \ra X
$$
such that it is easy for Nikita, say, to compute $E^{-1}$, but very
hard for anybody else to compute $E^{-1}$.
\subsection{How Nikita Makes an RSA Public Key}
Here is how Nikita makes a one-way function~$E$:
\begin{enumerate}
\item Nikita picks two large primes~$p$ and~$q$, and lets $n=pq$.
\item It is easy for Nikita to then compute
$$
\vphi(n) = \vphi(p)\cdot \vphi(q) = (p-1)\cdot (q-1).
$$
\item Nikita next chooses a ``random'' integer~$e$ with
$$
1**1$, a contradiction.
\vspace{0.3ex}
\noindent$\left(\Longleftarrow\right)$
Write $n=n_1^2 n_2$ where $n_2$ has no prime factors of the
form $4m+3$. It suffices to show that~$n_2$ is a sum of two
squares. Also note that
$$
(x_1^2 + y_1^2)(x_2^2+y_2^2) = (x_1x_2+y_1y_2)^2 + (x_1y_2-x_2y_1)^2,
$$
so a product of two numbers that are sums of two squares is also
a sum of two squares.\footnote{This algebraic identity is secretely
the assertion that the norm map $N:\Q(i)^* \ra \Q^*$ sending
$x+iy$ to $(x+iy)(x-iy)=x^2+y^2$ is a homomorphism.}
Also, the prime~$2$ is a sum of two squares.
It thus suffices to show that if~$p$ is a prime of the form
$4m+1$, then~$p$ is a sum of two squares.
Since
$$
(-1)^{\frac{p-1}{2}} = (-1)^{\frac{4m+1-1}{2}} = +1,
$$
$-1$ is a square modulo~$p$; i.e., there exists~$r$ such
that $r^2\con -1\pmod{p}$. Taking $n=\lfloor \sqrt{p}\rfloor$
in Lemma~\ref{lem:approx} we see that there are integers $a, b$
such that
$0 0$, so
$ax^2 + bxy+cy^2$ takes only positive or only negative values,
depending on the sign of~$a$. In this sense, $(a,b,c)$ is very
{\sf definite} about its choice of sign. If $\disc(a,b,c)>0$,
then $(2ax+by)^2 + (4ac-b^2)y^2$ takes both positive and negative
values, so $(a,b,c)$ does also.
We will consider only definite forms in the next two lectures.
\section{Real Life}
The following text is from the documentation for binary quadratic
forms in the {\sc Magma} computer algebra system. A quick scan of the
buzzwords emphasized (by me) below conveys an idea of where
binary quadratic forms appear in mathematics.
{\small
\begin{quote}
A binary quadratic form is an integral form $ax^2 + bxy + cy^2$ which
is represented in {\sc Magma} by a tuple $(a, b, c)$. Binary
quadratic forms play an central role in the {\em ideal theory of
quadratic fields}, the classical theory of {\em complex
multiplication}, and the theory of {\em modular forms}. Algorithms
for binary quadratic forms provide efficient means of computing in
the {\em ideal class group of orders} in a {\em quadratic field}. By
using the explicit relation of definite quadratic forms with lattices
with nontrivial endomorphism ring in the complex plane, one can apply
{\em modular and elliptic functions} to forms, and exploit the
analytic theory of complex multiplication.
The structures of quadratic forms of a given discriminant~$D$ correspond
to ordered bases of ideals in an order in a {\em quadratic number field},
defined up to scaling by the rationals. A form is primitive if the
coefficients $a$, $b$, and $c$ are coprime. For negative discriminants the
primitive reduced forms in this structure are in bijection with the
{\em class group of projective or invertible ideals}. For positive
discriminants, the reduced orbits of forms are used for this
purpose. Magma holds efficient algorithms for composition, enumeration
of reduced forms, {\em class group computations}, and
{\em discrete logarithms}. A
significant novel feature is the treatment of nonfundamental
discriminants, corresponding to nonmaximal orders, and the collections
of homomorphisms between different class groups coming from the
inclusions of these orders.
The functionality for binary quadratic forms is rounded out with
various functions for applying modular and elliptic functions to
forms, and for {\em class polynomials} associated to {\em class groups} of
definite forms.
\end{quote}
}
\renewcommand{\vtwo}[2]{\left[
\begin{matrix}#1\\#2
\end{matrix}\right]}
\chapter{Binary Quadratic Forms III: Reduction Theory}
Recall that a binary quadratic form is a function
$f(x,y) = ax^2 + bxy+cy^2$. Our motivating problem
is to decide which numbers are ``represented'' by~$f$;
i.e., for which integers~$n$ do there exist integers
$x, y$ such that $ax^2 + bxy + cy^2 = n$? If $g\in\SL_2(\Z)$
then $f(x,y)$ and $f|_g(x,y) = f\left(g\vtwo{x}{y}\right)$ represent
exactly the same set of integers. Also, $\disc(f)=\disc(f|_g)$,
where
$\disc(f) = b^2 - 4ac$,
and~$f$ is called {\em positive definite}
if $\disc(f)<0$ and $a>0$.
In today's lecture, we will learn about reduction theory, which
allows us to decide whether or not two positive definite binary
quadratic forms are equivalent under the action of $\SL_2(\Z)$.
If, in the future, you would like to pursue the theory of binary
quadratic forms in either a more algebraic or algorithmic direction, I
highly recommend that you look at Chapter~5 of Henri Cohen's book {\em
A Course in Computational Algebraic Number Theory} (GTM 138).
\section{Reduced Forms}
\begin{definition}[Reduced]
A positive definite quadratic form $(a,b,c)$ is {\em reduced}
if $|b|\leq a \leq c$ and if, in addition, when one of the
two inequalities is an equality (i.e., either $|b|=a$ or $a=c$),
then $b\geq 0$.
\end{definition}
There is a geometric interpretation of reduced, which we will not
use this later. Let $D=\disc(a,b,c) = b^2 - 4ac$ and set $\tau =
\frac{-b+\sqrt{D}}{2a}$, so $\tau$ is the root of $ax^2 + bx + c$
with positive imaginary part. The right action of $\SL_2(\Z)$ on
positive definite binary quadratic forms corresponds to the left
action of $\SL_2(\Z)$ by linear fractional transformations on the
complex upper half plane $\h = \{z \in \C : \Im(z)>0\}$. The standard
fundamental domain for the action of $\SL_2(\Z)$ on~$\h$ is
$$\mathcal{F} = \left\{\tau \in \h : \Re(\tau)\in\left[-\frac{1}{2},\frac{1}{2}\right),
|\tau|>1 \text{ or } |\tau|=1\text{ and }\Re(\tau)\leq 0\right\}.$$
Then $(a,b,c)$ is reduced if and only if the corresponding complex
number~$\tau$ lies in $\mathcal{F}$. For example, if $(a,b,c)$
is reduced then $\Re(\tau) = -b/2a\in[-1/2,1/2)$ since
$|b|\leq a$ and if $|b|=a$ then $b\geq 0$. Also
$$
|\tau| = \sqrt{\frac{b^2 + 4ac - b^2}{4a^2}}
= \sqrt{\frac{c}{a}} \geq 1$$
and if $|\tau|=1$ then $b\geq 0$ so $\Re(\tau) \leq 0$.
The following theorem (which is not proved in Davenport) highlights the
importance of reduced forms.
\begin{theorem}
There is exactly one reduced form in each equivalence class of
positive definite binary quadratic forms.
\end{theorem}
\begin{proof}
We have to prove two things. First, that every class contains at least
one reduced form, and second that this reduced form is the only
one in the class.
We first prove that there is a reduced form in every class.
Let $\mathcal{C}$ be an equivalence class of positive definite
quadratic forms of discriminant~$D$. Let~$(a,b,c)$ be
an element of $\mathcal{C}$ such that~$a$ is minimal (amongst elements
of $\mathcal{C}$). Note that for any such form we
have $c\geq a$, since $(a,b,c)$ is equivalent to
$(c,-b,a)$ (use the matrix $\abcd{0}{-1}{1}{\hfill 0}$).
Applying the element $\abcd{1}{k}{0}{1}\in\SL_2(\Z)$ to $(a,b,c)$
for a suitably chosen integer~$k$ (precisely,
$k=\lfloor(a-b)/2a\rfloor$) results in a form
$(a',b',c')$ with $a'=a$ and $b'\in (-a',a']$.
Since $a'=a$ is minimal, we have just as above that
$a'\leq c'$, hence
$(a',b',c')$ is ``just about'' reduced.
The only possible remaining problem would occur if $a'=c'$
and $b'<0$. In that case, changing $(a',b',c')$ to
$(c'',b'',a'')=(c',-b',a')$
results in an equivalent form with $b''>0$, so that
$(c'',b'',a'')$ is reduced.
Next suppose $(a,b,c)$ is a reduced form. We
will now establish that $(a,b,c)$ is the only reduced form
in its equivalence class. First, we check that~$a$ is minimal amongst all
forms equivalent to~$(a,b,c)$. Indeed, every other $a'$ has the
form $a'=ap^2 + bpr + cr^2$ with $p,r$ coprime integers (see this
by hitting $(a,b,c)$ by $\abcd{p}{q}{r}{s}$). The
identities
$$
a p^2 + bpr + c r^2 = a p^2 \left(1+\frac{b}{a}\frac{r}{p}\right)
+ cr^2 = a p^2 + c r^2\left( 1 + \frac{b}{c}\frac{p}{r}\right)
$$
then imply our claim since $|b|\leq a \leq c$
(use the first identity if $r/p<1$ and the second otherwise).
Thus any other reduced form $(a',b',c')$ equivalent to $(a,b,c)$
has $a'=a$. But the same identity implies that
the only forms equivalent to $(a,b,c)$ with $a'=a$ are obtained by applying
a transformation of the form $\mtwo{1}{k}{0}{1}$ (corresponding
to $p=1$, $r=0$). Thus $b' = b+2ak$ for some~$k$.
Since $a=a'$ we have $b,b'\in(-a,a]$, so $k=0$.
Finally
$$
c'=\frac{(b')^2-D}{4a'}=\frac{b^2-D}{4a} = c,
$$
so $(a',b',c')=(a,b,c)$.
\end{proof}
\section{Finding an Equivalent Reduced Form}
Here is how to find the reduced form equivalent
to a given positive definite form $(a,b,c)$.
This algorithm is useful for solving problems 8 and 9 on
the homework assignment.
Consider the following two operations, which can be used to diminish
one of~$a$ and $|b|$, without altering the other:
\begin{enumerate}
\item
If $ca$, replace $(a,b,c)$ by the equivalent form
$(a,b',c')$ where $b'=b+2ka$ and~$k$ is chosen so that
$b'\in(-a,a]$ (more precisely, $k=\lfloor \frac{a-b}{2a}\rfloor$),
and $c'$ is found from the fact that
$(b')^2 - 4ac'=D=\disc(a,b,c)$, so
$c' = \frac{(b')^2 - D}{4a}$.
\end{enumerate}
Starting with $(a,b,c)$, if you iterate the appropriate operation,
eventually you will find the reduced form that is equivalent to
$(a,b,c)$.
\begin{example}
Let $f=458x^2 + 214xy + 25y^2$.
\begin{center}
\begin{tabular}{|l|l|l|}\hline
Equivalent form & What I did & Matrix\\\hline
$(458,214,25)$ & & \\\hline
$(25,-214,458)$& (1) & $\abcd{0}{-1}{1}{0}$\\\hline
$(25,-14,2)$ & (2) with $k=4$ & $\abcd{1}{4}{0}{1}$\\\hline
$(2,14,25)$ & (1) & $\abcd{0}{-1}{1}{0}$\\\hline
$(2,2,1)$ & (2) with $k=-3$& $\abcd{1}{-3}{0}{1}$\\\hline
$(1,-2,2)$ & (1) & $\abcd{0}{-1}{1}{0}$\\\hline
$(1,0,1)$ & (2) with $k=1$ & $\abcd{1}{1}{0}{1}$\\\hline
\end{tabular}
\end{center}
Let
\begin{align*}
g &= \mtwo{0}{-1}{1}{0}\cdot \mtwo{1}{4}{0}{1}\cdot
\mtwo{0}{-1}{1}{0}\cdot \mtwo{1}{-3}{0}{1}\cdot
\mtwo{0}{-1}{1}{0}\cdot \mtwo{1}{1}{0}{1}\\
&= \mtwo{\hfill3}{\hfill4}{-13}{-17}.
\end{align*}
Then
$$f|_g = x^2 + y^2!$$
\end{example}
\section{Some PARI Code}
The following PARI code checks whether or not a form is reduced,
and computes the reduced form equivalent to a given form.
You can download it from my web page if you don't want to type
it in.
\begin{verbatim}
\\ true if and only if (a,b,c) is reduced.
{isreduced(a,b,c) =
if(b^2-4*a*c>=0 || a<0,
error("reduce: (a,b,c) must be positive definite."));
if(!(abs(b)<=a && a<=c), return(0));
if(abs(b)==a || a==c, return(b>=0));
return(1);
}
\\ reduces, printing out each step. returns the reduced form
\\ and a matrix that transforms the input form to the reduced form.
{reduce(a,b,c,s) =
local(D, k, t, g);
D=b^2-4*a*c;
if(D>=0 || a<0, error("reduce: (a,b,c) must be positive definite."));
g=[1,0;0,1];
while(!isreduced(a,b,c), \\ ! means ``not''
if(ca || -b==a,
k = floor((a-b)/(2*a));
b = b+2*k*a;
c = (b^2-D)/(4*a);
g = g*[1,k;0,1];
print([a,b,c], " \t(2) with k=",k)
)
)
);
return([a,b,c,g])
}
/* Here is an example:
? \r quadform
? reduce(458,214,25)
[25, -214, 458] (1)
[25, -14, 2] (2) with k=4
[2, 14, 25] (1)
[2, 2, 1] (2) with k=-3
[1, -2, 2] (1)
[1, 0, 1] (2) with k=1
%22 = [1, 0, 1, [3, 4; -13, -17]]
*/
\end{verbatim}
\chapter{Binary Quadratic Forms IV: The Class Group}
\section{Can You Hear the Shape of a Lattice?}
After Lecture 23, Emanuele Viola asked me whether or
not the following is true: {\em ``If $f_1$ and $f_2$ are binary quadratic
forms that represent exactly the same integers, is $f_1\sim f_2$?''}
The answer is no. For example,
$f_1=(2,1,3)=2x^2 + xy+3y^2$ and
$f_2=(2,-1,3)=2x^2 -xy+3y^2$
are inequivalent reduced positive definite binary quadratic
forms that represent exactly the same integers. Note that
$\disc(f_1) = \disc(f_2)=-23$.
There appears to be a sense in which
all counterexamples resemble the one just given.
Questions like these are central to John H. Conway's book {\em The
sensual (quadratic) form}, which I've never seen because the Cabot
library copy is checked out and the Birkhoff copy has gone missing. The
following is taken from the {\sc MathSciNet} review (I changed the
text slightly so that it makes sense):
\begin{quote}
Chapter~$2$ begins by posing Mark Kac's question of ``hearing the
shape of a drum'', and the author relates the higher-dimensional
analogue of this idea on tori---quotients of $\mathbf{R}\sp n$ by a
lattice---to the question of what properties of a positive definite
integral quadratic form are determined by the numbers the form
represents. A property of such a form is called ``audible'' if the
property is determined by these numbers, or equivalently, by the theta
function of the quadratic form. As examples, he shows that the
determinant of the form and the theta function of the dual form are
audible. He also provides counterexamples to the higher-dimensional
Kac question, the first of which were found by J. Milnor...
\end{quote}
\section{Class Numbers}
\begin{proposition}\label{prop:finite}
Let $D<0$ be a discriminant. There are only finitely
many equivalence classes of positive definite binary
quadratic forms of discriminant~$D$.
\end{proposition}
\begin{proof}
Since there is exactly one reduced binary quadratic form
in each equivalence class, it suffices to show that there are
only finitely many reduced forms of discriminant~$D$. Recall
that if a form $(a,b,c)$ is reduced, then
$|b| \leq a \leq c$.
If $(a,b,c)$ has discriminant~$D$ then $b^2-4ac=D$.
Since $b^2\leq a^2 \leq ac$, we have
$D = b^2-4ac\leq -3ac$, so
$$
3ac \leq -D.
$$
There are only finitely many positive integers $a,c$ that
satisfy this inequality.
\end{proof}
\begin{definition}
A binary quadratic form $(a,b,c)$ is {\em primitive}
if $\gcd(a,b,c)=1$.
\end{definition}
\begin{definition}
The {\em class number} $h_D$ of discriminant $D<0$ is the number
of equivalence classes of primitive positive definite binary
quadratic forms of discriminant~$D$.
\end{definition}
I computed the following table of class number $h_D$ for $-D\leq 839$
using the built-in PARI function {\tt qfbclassno(D,1)}.
Notice that there are just a few $1$s at the beginning and then no more.
\begin{center}
\begin{tabular}{|ll|}\hline
$-D$ & $h_{D}$\\\hline
3&{\bf 1}\\
7&{\bf 1}\\
11&{\bf 1}\\
15&2\\
19&{\bf 1}\\
23&3\\
27&{\bf 1}\\
31&3\\
35&2\\
39&4\\
43&{\bf 1}\\
47&5\\
51&2\\
55&4\\
59&3\\
63&4\\
67&{\bf 1}\\
71&7\\
75&2\\
79&5\\
83&3\\
87&6\\
91&2\\
95&8\\
99&2\\
103&5\\
107&3\\
111&8\\
115&2\\
119&10\\\hline
\end{tabular}
\begin{tabular}{|ll|}\hline
$-D$ & $h_{D}$\\\hline
123&2\\
127&5\\
131&5\\
135&6\\
139&3\\
143&10\\
147&2\\
151&7\\
155&4\\
159&10\\
163&{\bf 1}\\
167&11\\
171&4\\
175&6\\
179&5\\
183&8\\
187&2\\
191&13\\
195&4\\
199&9\\
203&4\\
207&6\\
211&3\\
215&14\\
219&4\\
223&7\\
227&5\\
231&12\\
235&2\\
239&15\\\hline
\end{tabular}
\begin{tabular}{|ll|}\hline
$-D$ & $h_{D}$\\\hline
243&3\\
247&6\\
251&7\\
255&12\\
259&4\\
263&13\\
267&2\\
271&11\\
275&4\\
279&12\\
283&3\\
287&14\\
291&4\\
295&8\\
299&8\\
303&10\\
307&3\\
311&19\\
315&4\\
319&10\\
323&4\\
327&12\\
331&3\\
335&18\\
339&6\\
343&7\\
347&5\\
351&12\\
355&4\\
359&19\\\hline
\end{tabular}
\begin{tabular}{|ll|}\hline
$-D$ & $h_{D}$\\\hline
363&4\\
367&9\\
371&8\\
375&10\\
379&3\\
383&17\\
387&4\\
391&14\\
395&8\\
399&16\\
403&2\\
407&16\\
411&6\\
415&10\\
419&9\\
423&10\\
427&2\\
431&21\\
435&4\\
439&15\\
443&5\\
447&14\\
451&6\\
455&20\\
459&6\\
463&7\\
467&7\\
471&16\\
475&4\\
479&25\\\hline
\end{tabular}
\begin{tabular}{|ll|}\hline
$-D$ & $h_{D}$\\\hline
483&4\\
487&7\\
491&9\\
495&16\\
499&3\\
503&21\\
507&4\\
511&14\\
515&6\\
519&18\\
523&5\\
527&18\\
531&6\\
535&14\\
539&8\\
543&12\\
547&3\\
551&26\\
555&4\\
559&16\\
563&9\\
567&12\\
571&5\\
575&18\\
579&8\\
583&8\\
587&7\\
591&22\\
595&4\\
599&25\\\hline
\end{tabular}
\begin{tabular}{|ll|}\hline
$-D$ & $h_{D}$\\\hline
603&4\\
607&13\\
611&10\\
615&20\\
619&5\\
623&22\\
627&4\\
631&13\\
635&10\\
639&14\\
643&3\\
647&23\\
651&8\\
655&12\\
659&11\\
663&16\\
667&4\\
671&30\\
675&6\\
679&18\\
683&5\\
687&12\\
691&5\\
695&24\\
699&10\\
703&14\\
707&6\\
711&20\\
715&4\\
719&31\\\hline
\end{tabular}
\begin{tabular}{|ll|}\hline
$-D$ & $h_{D}$\\\hline
723&4\\
727&13\\
731&12\\
735&16\\
739&5\\
743&21\\
747&6\\
751&15\\
755&12\\
759&24\\
763&4\\
767&22\\
771&6\\
775&12\\
779&10\\
783&18\\
787&5\\
791&32\\
795&4\\
799&16\\
803&10\\
807&14\\
811&7\\
815&30\\
819&8\\
823&9\\
827&7\\
831&28\\
835&6\\
839&33\\\hline
\end{tabular}
\end{center}
We can compute these numbers using Proposition~\ref{prop:finite}.
The following PARI program enumerates the primitive reduced
forms of discriminant~$D$.
\begin{verbatim}
{isreduced(a,b,c) =
if(b^2-4*a*c>=0 || a<0,
error("reduce: (a,b,c) must be positive definite."));
if(!(abs(b)<=a && a<=c), return(0));
if(abs(b)==a || a==c, return(b>=0));
return(1);
}
{reduce(f) =
local(D, k, t, a,b,c);
a=f[1]; b=f[2]; c=f[3]; D=b^2-4*a*c;
if(D>=0 || a<0, error("reduce: (a,b,c) must be positive definite."));
while(!isreduced(a,b,c), \\ ! means ``not''
if(ca || -b==a,
k = floor((a-b)/(2*a));
b = b+2*k*a;
c = (b^2-D)/(4*a);
)
)
);
return([a,b,c])
}
{reducedforms(D)=
local(bound, forms, b, r);
if (D > 0 || D%4 == 2 || D%4==3, error("Invalid discriminant"));
bound = floor(-D/3);
forms = [];
for(a = 1, bound,
for(c = 1, bound,
if(3*a*c<=-D && issquare(4*a*c+D),
b = floor(sqrt(4*a*c+D));
r = reduce([a,b,c]);
print1([a,b,c], " ----> ", r);
if (gcd(r[1],gcd(r[2],r[3])) == 1,
forms = setunion(forms,[r]); print(""),
\\ else
print (" \t(not primitive)")
)
)
)
);
return(eval(forms)); \\ eval gets rid of the annoying quotes.
}
\end{verbatim}
For example, when $D=-419$ the program finds exactly $9$ reduced forms:
\begin{verbatim}
? D = -419
%21 = -419
? qfbclassno(D,1)
%22 = 9
? reducedforms(D)
[1, 1, 105] ----> [1, 1, 105]
[1, 3, 107] ----> [1, 1, 105]
[1, 5, 111] ----> [1, 1, 105]
[1, 7, 117] ----> [1, 1, 105]
[1, 9, 125] ----> [1, 1, 105]
[1, 11, 135] ----> [1, 1, 105]
[3, 1, 35] ----> [3, 1, 35]
[3, 5, 37] ----> [3, -1, 35]
[3, 7, 39] ----> [3, 1, 35]
[3, 11, 45] ----> [3, -1, 35]
[5, 1, 21] ----> [5, 1, 21]
[5, 9, 25] ----> [5, -1, 21]
[5, 11, 27] ----> [5, 1, 21]
[7, 1, 15] ----> [7, 1, 15]
[9, 7, 13] ----> [9, 7, 13]
[9, 11, 15] ----> [9, -7, 13]
[13, 7, 9] ----> [9, -7, 13]
[15, 1, 7] ----> [7, -1, 15]
[15, 11, 9] ----> [9, 7, 13]
[21, 1, 5] ----> [5, -1, 21]
[25, 9, 5] ----> [5, 1, 21]
[27, 11, 5] ----> [5, -1, 21]
[35, 1, 3] ----> [3, -1, 35]
[37, 5, 3] ----> [3, 1, 35]
[39, 7, 3] ----> [3, -1, 35]
[45, 11, 3] ----> [3, 1, 35]
[105, 1, 1] ----> [1, 1, 105]
[107, 3, 1] ----> [1, 1, 105]
[111, 5, 1] ----> [1, 1, 105]
[117, 7, 1] ----> [1, 1, 105]
[125, 9, 1] ----> [1, 1, 105]
[135, 11, 1] ----> [1, 1, 105]
%23 = [[1, 1, 105], [3, -1, 35], [3, 1, 35], [5, -1, 21], [5, 1, 21],
[7, -1, 15], [7, 1, 15], [9, -7, 13], [9, 7, 13]]
? length(%23)
%24 = 9
\end{verbatim}
\begin{theorem}[Heegner, Stark-Baker, Goldfeld-Gross-Zagier]
Suppose~$D$ is a negative discriminant that is either square
free or~$4$ times a square-free number. Then
\begin{itemize}
\item $h_D=1$ only for $D=-3,-4,-7,-8,-11,-19,-43,-67,-163$.
\item $h_D=2$ only for $D=-15, -20, -24, -35, -40, -51, -52, -88, -91,$\\
$ -115,-123, -148, -187, -232, -235, -267, -403, -427$.
\item $h_D=3$ only for $D=-23,-31,-59,-83,-107,-139,-211,-283,-307,$\\
$-331,-379,-499,-547,-643,-883,-907.$
\item $h_D=4$ only for $D=-39,-55,-56,-68,\ldots,-1555.$
\end{itemize}
\end{theorem}
To quote Henri Cohen: ``The first two statements concerning class
numbers~$1$ and~$2$ are very difficult theorems proved in 1952 by
Heegner and in 1968--1970 by Stark and Baker. The general problem of
determing all imaginary quadratic fields with a given class number has
been solved in principle by Goldfeld-Gross-Zagier, but to my
knowledge the explicit computations have been carried to the end
only for class numbers~$3$ and~$4$ (in addition to the already known
class numbers~$1$ and~$2$).
\section{The Class Group}
There are {\em much} more sophisticated ways to compute $h_D$ than
simply listing the reduced binary quadratic forms of discriminant~$D$,
which is an $O(|D|)$ algorithm. For example, there is an algorithm
that can compute $h_D$ for $D$ having $50$ digits in a reasonable
amount of time. These more sophisticated algorithms use the fact
that the set of primitive positive definite binary quadratic forms
of given discriminant is a finite abelian group.
\begin{definition}
Let $f_1=(a_1,b_1,c_1)$ and $f_2=(a_2,b_2,c_2)$ be two
quadratic forms of the same discriminant~$D$. Set
$s=(b_1+b_2)/2$, $n=(b_1-b_2)/2$ and let $u,v,w$ and~$d$
be such that
$$
u a_1 + v a_2 + w s = d = \gcd(a_1, a_2, s)
$$
(obtained by two applications of Euclid's algorithm), and let
$d_0 = \gcd(d,c_1,c_2,n)$. Define the composite of the equivalence
classes of the two forms $f_1$ and $f_2$ to be
the equivalence class of the form
$$
(a_3, b_3, c_3) = \left(
d_0 \frac{a_1 a_2}{d^2},
b_2 + \frac{2a_2}{d}(v(s-b_2)-w c_2),
\frac{b_3^2-D}{4a_3}\right).
$$
\end{definition}
This mysterious-looking group law is induced by ``multiplication
of ideals'' in the ``ring of integers'' of the quadratic imaginary
number field $\Q(\sqrt{D})$.
The following PARI program computes this group operation:
\begin{verbatim}
{composition(f1, f2)=
local(a1,b1,c1,a2,b2,c2,D,s,n,bz0,bz1,u,v,w);
a1=f1[1]; b1=f1[2]; c1=f1[3];
a2=f2[1]; b2=f2[2]; c2=f2[3];
D = b1^2 - 4*a1*c1;
if(b2^2 - 4*a2*c2 != D, error("Forms must have the same discriminant."));
s = (b1+b2)/2;
n = (b1-b2)/2;
bz0 = bezout(a1,a2);
bz1 = bezout(bz0[3],s);
u = bz1[1]*bz0[1];
v = bz1[1]*bz0[2];
w = bz1[2];
d = bz1[3];
d0 = gcd(gcd(gcd(d,c1),c2),n);
a3 = d0*a1*a2/d^2;
b3 = b2+2*a2*(v*(s-b2)-w*c2)/d;
c3 = (b3^2-D)/(4*a3);
f3 = reduce([a3,b3,c3]);
return(f3);
}
\end{verbatim}
Let's try the group out in the case when $D=-23$.
\begin{verbatim}
? reducedforms(-23)
[1, 1, 6] ----> [1, 1, 6]
[2, 1, 3] ----> [2, 1, 3]
[3, 1, 2] ----> [2, -1, 3]
[6, 1, 1] ----> [1, 1, 6]
%56 = [[1, 1, 6], [2, -1, 3], [2, 1, 3]]
\end{verbatim}
Thus the group has elements $(1,1,6)$, $(2,-1,3)$, and $(2,1,3)$.
Since $h_{-23}=3$,
the group must be cyclic of order~$3$. Let's find the identity element.
\begin{verbatim}
? composition([1,1,6],[2,-1,3])
%58 = [2, -1, 3]
\end{verbatim}
Thus the identity element must be $(1,1,6)$.
The element $(2,-1,3)$ is a generator for the group:
\begin{verbatim}
? composition([2,-1,3],[2,-1,3])
%59 = [2, 1, 3]
? composition([2,-1,3],[2,1,3])
%60 = [1, 1, 6]
\end{verbatim}
\chapter{Elliptic Curves 1: Introduction}
\section{The Definition}
Finally we come to elliptic curves, which I think are the most
exciting and central {\em easily accessibly} objects in modern number
theory. There are so many exciting things to tell you about elliptic
curves, that the course is suddenly going to move more quickly
than before.
\begin{definition}
An {\em elliptic curve}~$E$ over a field~$K$ is a plane cubic
curve of the form
$$
y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6,
$$
where
$ a_1, a_2, a_3, a_4, a_6 \in K$
and
$$
\Delta = -b_2^2 b_8 - 8b_4^3 - 27 b_6^2 + 9b_2 b_4 b_6 \neq 0,
$$
where
$$b_2 = a_1^2 + 4a_2, \quad b_4 = 2a_4 + a_1 a_3,\quad
b_6 = a_3^2 + 4a_6.
$$
\end{definition}
Help! Don't worry, when $2$ and $3$ are not equal to $0$ in $K$, using
completing the square and a little algebra we find a change of
coordinates that transforms the above cubic equation into the form
$$
y^2 = x^3 + ax + b,
$$
and then $\Delta = -16(4a^3 + 27b^2)$.
We will consider only elliptic curves of the form $y^2 = x^3 + ax+b$
for a while.
Hey! That's not an ellipse! You're right, elliptic curves are {\em
not ellipses}; they are curves that first arose when $19$th century
mathematicians studied integral formulas for the arc lengths of
ellipses.
In these lectures, I'll give you a glimpse into two main ways in which
elliptic curves feature in mathematics. On the left hand, they
provide the simplest example of a class of diophantine equations that
we still can't totally solve. On the right hand, when~$K$ is a finite
field (or, more sneakily, a finite ring), elliptic curves can be used
as a tool for both making and breaking cryptosystems.
\section{Linear and Quadratic Diophantine Equations}
Consider the following question:
\begin{quote}
Let $F(x,y)$ be an irreducible polynomial in two variables over~$\Q$.
Find all rational numbers $x_0,y_0$ such that
$
F(x_0, y_0) = 0.
$
\end{quote}
When $F$ is linear, this problem is easy. The equation
$$
F(x,y) = ax + by + c = 0
$$
defines a line, and letting $y=t$, the solutions are
$$
\left\{ \left( -\frac{b}{a} t - \frac{c}{a}, t\right)
\, : \, t \in \Q\right\}.
$$
When~$F$ is quadratic, the solution is not completely trivial, but it
is well understood. In this case, the equation $F=0$ has infinitely
many rational solutions if and only if it has at least one solution.
Moreover, it is easy to describe all solutions when there is one. If
$(x_0, y_0)$ is a solution and $L$ is a non-tangent line through
$(x_0,y_0)$, then~$L$ will intersect the curve $F=0$ in exactly one
other point $(x_1, x_1)$. Also $x_1, y_1\in\Q$ since a quadratic
polynomial over~$\Q$ with $1$ rational root has both roots rational.
Thus the rational points on $F=0$ are in bijection with the slopes of
lines through $(x_0,y_0)$.
Chapter 2 of [Kato et al.] is about how to decide whether
or not an~$F$ of degree~$2$ has a rational point. The answer is that
$F=0$ has a rational solution if and only if $F=0$ has a solution with
$x_0,y_0\in\R$ and a solution with $x_0,y_0\in\Q_p$ for every
``$p$-adic field'' $\Q_p$. This condition, though it might sound
foreboding, is easy to check in practice. I encourage you to
flip through chapter 2 of loc. cit.
\section{Points on Elliptic Curves}
Next suppose that~$F$ is an irreducible cubic polynomial.
The question of whether or not $F=0$ has a rational solution is
still an {\em open problem}! We will not consider this problem
further until we discuss the Birch and Swinnerton-Dyer conjecture.
Suppose that $F=0$ has a given rational solution. Then one can change
coordinates so that the question of finding the rational solutions to
$F=0$ is equivalent to the problem of finding all rational points on
the elliptic curve
$$
y^2 = x^3 + ax + b.
$$
Recall that when~$F$ has degree~$2$ we can use a given rational
point~$P$ on the graph of $F=0$ to find all other rational points by
intersecting a line through~$P$ with the graph of $F=0$.
The graph of $y^2=x^3+ax+b$ looks like
\begin{center}
[egg and curvy line] or [curvier line]
\end{center}
Notice that if~$P$ is a point on the graph of the curve, then a line
through~$P$ (usually) intersects the graph in exactly {\em two} other
points. In general, these two other points usually do not have
rational coordinates. However, if~$P$ and~$Q$ are rational points on
the graph of $y^2=x^3+ax+b$ and~$L$ is the line through~$P$ and~$Q$,
then the third point of intersection with the graph will have rational
coordinates. Explicitly, if $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ then the
third point of intersection has coordinates\footnote{It is traditional
in a course like ours for me to derive these formulas. I'm not going
to, because it's simple algebra and once you see the geometric picture
it is easy to carry out. You should do this as an exercise, or read
the derivation in [Kato et al.] or [Davenport].}
$$
x_3 = \left(\frac{y_2 - y_1}{x_2-x_1}\right)^2 - x_1 - x_2, \qquad
y_3 = \frac{y_2-y_1}{x_2-x_1} x_3 - \frac{y_2 x_1 - y_1 x_2}{x_2-x_1}.
$$
Thus, given two points on $E$, we can find another. Also, given a single
point, we can draw the tangent line to $E$ through that point and obtain
a third point.
\subsection{To Infinity!}
At first glance, the above construction doesn't work if $x_1=x_2$.
[draw picture]. Fortunately, there is a natural sense in which the
graph of~$E$ is missing one point, and when $x_1=x_2$ this one
missing point is the third point of intersection.
The graph of~$E$ that we drew above is a graph in the plan $\R^2$.
The plane is a subset of the projective plane $\P^2$, which I will
define in just a moment. The closure of the graph of $y^2 = x^3 +ax+b$
in $\P^2$ has exactly one extra point, which has rational coordinates,
and which we denote by~$\infty$.
Formally, $\P^2$ can be viewed as the set of triples $(a,b,c)$
with $a,b,c$ not all~$0$ modulo the equivalence relation
$$(a,b,c)\sim (\lambda a ,\lambda b , \lambda c)$$
for any nonzero $\lambda$.
Denote by $(a:b:c)$ the equivalence class of $(a,b,c)$.
The closure of the graph of $y^2 = x^3 + ax+b$ is the
graph of
$
y^2 z = x^3 + axz^2 + bz^3
$
and the extra point $\infty$ is $(0:1:0)$.
\hd{Venerable Problem:} Find an algorithm that, given
an elliptic curve~$E$ over~$\Q$, outputs a complete description
of the set of rational points $(x_0, y_0)$ on~$E$.
This problem is difficult. In fact, so far it has stumped everyone!
There is a conjectural algorithm, but nobody has succeeded in proving
that it is really an algorithm, in the sense that it terminates for
any input curve~$E$. Several of your profs at Harvard, including
Barry Mazur, myself, and Christophe Cornut (who will teach Math 129
next semester) have spent, or will probably spend, a huge chunk of
their life thinking about this problem. (Am I being overly pessimistic?)
How could one possible ``describe'' the set of rational points on~$E$
in the first place? In 1923, Louis Mordell proved an amazing theorem,
which implies that there is a reasonable way to describe the rational
points on~$E$. To state his theorem, we introduce the ``group law''
on~$E$.
\section{The Group Law}
Consider the set
$
E(\Q) = \{\infty\} \union
\{ (x_0, y_0) : y_0^2 = x_0^3 + ax_0 + b\}.
$
There is a natural way to endow the set $E(\Q)$ with a {\em group}
structure. Here's how it works. First, the element $\infty\in E(\Q)$
is the $0$ element of the group. Next, suppose $P$ and $Q$ are elements of
$E(\Q)$. Just like we did earlier, draw the line through $P$ and $Q$
and let $R=(x_3,y_3)$ be the third point of intersection. Define
$
P + Q = (x_3, -y_3).
$
There are various special cases to consider, such as when $P=Q$ or
the third point of intersection is $\infty$, but I will let your read about
them in [Kato et al.]. It is clear that this binary operation on $E(\Q)$
satisfies $P+Q = Q+P$. Also, the inverse of $P=(x_1,y_1)$ is
$-P=(x_1,-y_1)$. The only other axiom to check in order to
verify that $+$ gives $E(\Q)$ an abelian group structure is the associative
law. This is simple but {\em very tedious} to check using only elementary
methods\footnote{The right way to prove that the associate law holds is to
develop the theory of algebraic curves and define the group law in
terms of divisors; this is way outside the scope of this course.}.
Fortunately, we can coerce the computer algebra system MAGMA
into verifying the associative law for us:
\begin{verbatim}
// The field K = Q(a,b,x0,x1,x2)
K := FieldOfFractions(PolynomialRing(Rationals(),5));
// The polynomial ring R = K[y0,y1,y2]
R**

0$, show that $$ [a_n,a_{n-1},\ldots, a_1, a_0] = \frac{p_n}{p_{n-1}} $$ and $$ [a_n,a_{n-1},\ldots, a_2, a_1] = \frac{q_n}{q_{n-1}}. $$ (Hint: In the first case, notice that $\frac{p_n}{p_{n-1}} = a_n + \frac{p_{n-2}}{p_{n-1}} = a_n + \frac{1}{\frac{p_{n-1}}{p_{n-2}}}.$) \item (4 points) There is a function~$j(\tau)$, denoted by {\tt ellj} in PARI, which takes as input a complex number~$\tau$ with positive imaginary part, and returns a complex number called the ``$j$-invariant of the associated elliptic curve''. Suppose that~$\tau$ is {\em approximately} $-0.5+ 0.3281996289i$ and that you know that~$j=j(\tau)$ is a rational number. Use continued fractions and PARI to compute a reasonable guess for the rational number $j=\mbox{\tt ellj}(\tau)$. (Hint: In PARI $\sqrt{-1}$ is represented by {\tt I}.) \item (3 points) Evaluate each of the following infinite continued fractions: \begin{subprob} \item $[\overline{2,3}]$ \item $[2,\overline{1,2,1}]$ \item $[0,\overline{1,2,3}]$ \end{subprob} \item (3 points) Determine the infinite continued fraction of each of the following numbers: \begin{subprob} \item $\sqrt{5}$ \item $\ds\frac{1+\sqrt{13}}{2}$ \item $\ds\frac{5+\sqrt{37}}{4}$ \end{subprob} \newpage \item \begin{subprob} \item (4 points) For any positive integer~$n$, prove that $ \sqrt{n^2+1} = [n,\overline{2n}].$ \item (2 points) Find a convergent to $\sqrt{5}$ that approximates $\sqrt{5}$ to within four decimal places. \end{subprob} \item (4 points) A famous theorem of Hurwitz (1891) says that for any irrational number~$x$, there exists infinitely many rational numbers $a/b$ such that $$\left| x - \frac{a}{b}\right| < \frac{1}{\sqrt{5}b^2}.$$ Taking $x=\pi$, obtain three rational numbers that satisfy this inequality. \item (3 points) The continued fraction expansion of~$e$ is $$ [2,1,2,1,1,4,1,1,6,1,1,8,1,1,\ldots]. $$ It is a theorem that the obvious pattern continues indefinitely. Do you think that the continued fraction expansion of $e^2$ also exhibits a nice pattern? If so, what do you think it is? \item \begin{subprob} \item (4 points) Show that there are infinitely many even integers~$n$ with the property that both $n+1$ and $\frac{n}{2}+1$ are perfect squares. \item (3 points) Exhibit two such integers that are greater than $389$. \end{subprob} \item (7 points) A primitive Pythagorean triple is a triple $x, y, z$ of integers such that $x^2 + y^2 = z^2$. Prove that there exists infinitely many primitive Pythagorean triples $x, y, z$ in which~$x$ and~$y$ are consecutive integers. \end{problems} \section{Binary Quadratic Forms} \begin{problems} \item (3 points) Which of the following numbers is a sum of two squares? Express those that are as a sum of two squares. $$ -389,\,\, 12345, \,\,91210,\,\,729,\,\, 1729,\,\, 68252 $$ \item \begin{subprob} \item (4 points) Write a PARI program that takes a positive integer~$n$ as input and outputs a sequence {\tt [x,y,z,w]} of integers such that $x^2 + y^2 + z^2 + w^2=n$. (Hint: Your program does not have to be efficient.) \item (2 point) Write $2001$ as a sum of three squares. \end{subprob} \item (3 points) Find a positive integer that has a least three different representations as the sum of two squares, disregarding signs and the order of the summands. \item (5 points) Show that a natural number~$n$ is the sum of two integer squares if and only if it is the sum of two rational squares. \item (6 points) Mimic the proof of the main theorem of Lecture 21 to show that an odd prime~$p$ is of the form $8m+1$ or $8m+3$ if and only if it can be written as $p=x^2 + 2y^2$ for some choice of integers~$x$ and~$y$. (Hint: Use the formula for the quadratic residue symbol $\kr{-2}{p}$ from Lecture 13.) \item (4 points) A {\em triangular number} is a number that is the sum of the first $m$ integers for some positive integer~$m$. If~$n$ is a triangular number, show that all three of the integers $8n^2$, $8n^2+1$, and $8n^2+2$ can be written as a sum of two squares. \item (3 points) Prove that of any four consecutive integers, at least one is not representable as a sum of two squares. \item (4 points) Show that $13x^2+36xy+25y^2$ and $58x^2+82xy+29y^2$ are each equivalent to the form $x^2+y^2$, then find integers~$x$ and~$y$ such that $13x^2+36xy+25y^2 = 389$. \item (4 points) What are the discriminants of the forms $199x^2-162xy+33y^2$ and $35x^2-96xy+66y^2$? Are these forms equivalent? %\item (6 points) Use results about quadratic forms to show %that a prime~$p$ can be written as $p = x^2 + 3y^2$ if and only %if $p=3$ or $p\con 1\pmod{6}$. \end{problems} \section{Class Groups and Elliptic Curves} \begin{problems} \item (10 points) For any negative discriminant~$D$, let $C_D$ denote the finite abelian group of equivalence classes of primitive positive definite quadratic forms of discriminant~$D$. Use the PARI program {\tt forms.gp} from lecture 24 (download it from my web page) to compute representatives for $C_D$ and determine the structure of $C_D$ as a produce of cyclic groups for each of the following five values of~$D$: $$ D=-155, -231, -660, -12104, -10015. $$ \item (6 points) Draw a beautiful graph of the set $E(\R)$ of real points on each of the following elliptic curves: \begin{subprob} \item $y^2 = x^3 - 1296x + 11664$, \item $y^2 + y = x^3 - x$, \item $y^2 + y = x^3 - x^2 - 10x - 20$. \end{subprob} \item (4 points) A rational solution to the equation $y^2-x^3=-2$ is $(3,5)$. Find a rational solution with $x\neq 3$ by drawing the tangent line to $(3,5)$ and computing the third point of intersection. \end{problems} \section{Elliptic Curves I} \begin{problems} \item (3 points) Consider the elliptic curve $y^2 + xy + y = x^3$ over $\Q$. Find a linear change of variables that transforms this curve into a curve of the form $Y^2 = X^3+a X + b$ for rational numbers~$a$ and~$b$. \item (6 points) Let~$E$ be the elliptic curve over the finite field $K=\Z/5\Z$ defined by the equation $$ y^2 = x^3 + x +1. $$ \begin{subprob} \item List all~$9$ elements of~$E(K)$. \item What is the structure of the group $E(K)$, as a product of cyclic groups? \end{subprob} \item (8 points) Let~$E$ be an elliptic curve over~$\Q$. Define a binary operation $\boxplus$ on~$E$ as follows: $$P \boxplus Q = -(P+Q).$$ Thus the $\boxplus$ of~$P$ and~$Q$ is the third point of intersection of the line through~$P$ and~$Q$ with~$E$. \begin{subprob} \item Lists the axiom(s) of a group that fail for $E(\R)$ equipped with this binary operation. (The group axioms are ``identity'', ``inverses'', and ``associativity''.) \item Under what conditions on $E(\Q)$ does this binary operation define a group structure on $E(\Q)$? (E.g., when $E(\Q)=\{\mathcal{O}\}$ this binary operation does define a group.) \end{subprob} \item (6 points) Let $g(t)$ be a quartic polynomial with distinct (complex) roots, and let~$\alpha$ be a root of $g(t)$. Let $\beta\neq 0$ be any number. \begin{subprob} \item Prove that the equations $$ x = \frac{\beta}{t-\alpha}, \qquad y = x^2 u = \frac{\beta^2 u}{(t-\alpha)^2} $$ give an ``algebraic transformation'' between the curve $u^2=g(t)$ and the curve $y^2=f(x)$, where $f(x)$ is the cubic polynomial $$ f(x) = g'(\alpha) \beta x^3 + \frac{1}{2} g''(\alpha) \beta^2 x^2 + \frac{1}{6}g'''(\alpha) \beta^3 x + \frac{1}{24} g''''(\alpha)\beta^4. $$ \item Prove that if~$g$ has distinct (complex) roots, then~$f$ also has distinct roots, and so $u^2 = g(t)$ is an elliptic curve. \end{subprob} \item (8 points) In this problem you will finally find out exactly why elliptic curves are called ``elliptic curves''! Let $0<\beta\leq \alpha$, and let $C$ be the ellipse $$\frac{x^2}{\alpha^2} + \frac{y^2}{\beta^2} = 1.$$ \begin{subprob} \item Prove that the arc length of~$C$ is given by the integral $$ 4\alpha\int_{0}^{\pi/2} \sqrt{1-k^2\sin^2\theta} d\theta $$ for an appropriate choice of constant~$k$ depending on~$\alpha$ and~$\beta$. \item Check your value for~$k$ in (i) by verifying that when $\alpha=\beta$, the integral yields the correct value for the arc length of a circle. \item Prove that the integral in (i) is also equal to $$ 4\alpha\int_0^1 \sqrt{\frac{1-k^2t^2}{1-t^2}} dt = 4\alpha\int_0^1\frac{1-k^2t^2}{\sqrt{(1-t^2)(1-k^2t^2)}}dt. $$ \item Prove that if the ellipse $E$ is not a circle, then the equation $$ u^2 = (1-t^2)(1-k^2t^2) $$ defines an elliptic curve (cf. the previous exercise). Hence the problem of determining the arc length of an ellipse comes down to evaluating the integral $$ \int_0^1 \frac{1-k^2t^2}{u} dt $$ on the ``elliptic'' curve $u^2=(1-t^2)(1-k^2t^2)$. \end{subprob} \item (8 points) Suppose that $P=(x,y)$ is a point on the cubic curve $$ y^2 = x^3 + ax + b. $$ \begin{subprob} \item Verify that the~$x$ coordinate of the point $2P$ is given by the duplication formula $$ x(2P) = \frac{x^4 - 2ax^2 -8bx +a^2}{4y^2}. $$ \item Derive a similar formula for the $y$ coordinate of $2P$ in terms of~$x$ and~$y$. \item Find a polynomial in~$x$ whose roots are the $x$-coordinates of the points $P=(x,y)$ satisfying $3P=\mathcal{O}$. [Hint: The relation $3P=\mathcal{O}$ can also be written $2P=-P$.] \item For the particular curve $y^2 = x^3 + 1$, solve the equation in (iii) to find all of the points satisfying $3P=\mathcal{O}$. Note that you will have to use complex numbers. \end{subprob} \end{problems} \section{Elliptic Curves II} \begin{problems} \item (10 points) Let $\Phi$ be the set of the $15$ possible groups of the form $E(\Q)_{\tor}$ for~$E$ an elliptic curve over~$\Q$ (see Lecture~27). For each group $G\in\Phi$, if possible, find a finite field $k = \Z/p\Z$ and an elliptic curve~$E$ over~$k$ such that $E(k) \ncisom G$. (Hint: It is a fact that $|p + 1 - \#E(\Z/p\Z))| \leq 2\sqrt{p}$, so you only have to try finitely many~$p$ to show that a group~$G$ does not occur as the group of points on an elliptic curve over a finite field.) %\item (5 points) Demonstrate how to use the Lutz-Nagell theorem %(Lecture~27) to compute the torsion subgroup of the elliptic %curve defined by the equation %$$y^2 +xy = x^3 -8369487776175x + 9319575518172005625.$$ \item (6 points) Many number theorists, such as myself one week ago, incorrectly think that Lutz-Nagell works well in practice. Describe the steps you {\em would} take if you were to use the Lutz-Nagell theorem (Lecture~27) to compute the torsion subgroup of the elliptic curve~$E$ defined by the equation $$y^2 +xy = x^3 -8369487776175x + 9319575518172005625,$$ then tell me why it would be {\em very} time consuming to actually carry these steps out. Find the torsion subgroup of~$E$ using the {\tt elltors} command in PARI. Does {\tt elltors} use the Lutz-Nagell algorithm by default? \item (6 points) Let $E$ be the elliptic curve defined by the equation $y^2 = x^3 +1$. \begin{subprob} \item For each prime $p$ with $5\leq p<30$, describe the group of points on this curve having coordinates in the finite field $\Z/p\Z$. (You can just give the order of each group.) \item For each prime in (i), let $N_p$ be the number of points in the group. (Don't forget the point infinity.) For the set of primes satisfying $p\con 2\pmod{3}$, can you see a pattern for the values of $N_p$? Make a general conjecture for the value of $N_p$ when $p\con 2\pmod{3}$. \item Prove your conjecture. \end{subprob} \item (6 points) Let~$p$ be a prime and let $E$ be the elliptic curve defined by the equation $y^2 = x^3 +px$. Use Lutz-Nagel to find all points of finite order in $E(\Q)$. \item (4 points) \begin{subprob} \item Let~$E$ be an elliptic curve over the real numbers~$\R$. Prove that $E(\R)$ is not a finitely generated abelian group. \item Let~$E$ be an elliptic curve over a finite field $k=\Z/p\Z$. Prove that $E(k)$ is a finitely generated abelian group. \end{subprob} \end{problems} \section{Elliptic Curves III} \begin{problems} \item (5 points) Make up a simple example that illustrates how to use the ElGamal elliptic curve cryptosystem (see Lecture 29). You may mention Nikita and Michael if you wish. Be very clear about what you are illustrating so that the grader can effortlessly understand your example. \item (5 points) Make up an example that illustrates an interesting aspect of the Pollard $(p-1)$ factorization method. \item (5 points) Make up an example that illustrates something that you consider an interesting aspect of Lenstra's elliptic curves factorization method. \item (10 points) Let~$R$ be a ring. We say that Fermat's last theorem is false in~$R$ if there exists $x,y,z\in R$ and $n\in \mathbb{Z}$ with $n\geq 3$ such that $x^n + y^n = z^n$ and $xyz\neq 0$. For which prime numbers~$p$ is Fermat's last theorem false in the ring $\mathbb{Z}/p\mathbb{Z}$?\footnote{This problem was on the dreaded Harvard graduate school qualifying examination this year. Every one of the students who took that exam got this problem right.} \end{problems} \end{document}