\documentclass{article}1\include{macros}2\newcommand{\url}[1]{\begin{center}{\tt #1}\end{center}}3\newcommand{\code}[1]{{\blue\tt #1}}4\usepackage{graphicx}5\usepackage{color}6\usepackage{pstricks}7\title{The Congruent Number Problem:\\A Thousand Year Old Unsolved Problem}8\author{William Stein ({\tt http://modular.math.washington.edu})}9\date{SIMUW 2006}1011\newcommand{\computation}{{\blue\sc\underline{Computation}:} }12\newcommand{\theory} {{\blue\sc\underline{Theory}:} }13\newcommand{\research}{{\blue\sc\underline{Research}:} }14\renewcommand{\sage}{{\blue\SAGE\xspace}}1516\begin{document}17\maketitle1819\begin{abstract}20One of the oldest unsolved problems in mathematics is to determine21the {\em congruent numbers}: {\em Give a way to decide whether or22not an integer is the area of a right triangle with rational side23lengths.} For example, 6 is the area of the right triangle with24side lengths 3, 4, and 5. But 1 is not a congruent number. What25about 2006? This workshop will take us from ancient algebra to a26major modern conjecture in number theory that has a million dollar27bounty: the Birch and Swinnerton-Dyer Conjecture.28\end{abstract}\vspace{-7ex}2930\begin{center}31\includegraphics[width=0.7\textwidth]{graphics/tri}\vspace{-7ex}32\end{center}33The first few congruent numbers:34{\tiny\noindent{}5, 6, 7, 13, 14, 15, 20, 21, 22, 23, 24, 28, 29, 30, 31, 34,3537, 38, 39, 41, 45, 46, 47, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65,3669, 70, 71, 77, 78, 79, 80, 84, 85, 86, 87, 88, 92, 93, 94, 95, 96,37101, 102, 103, 109, 110, 111, 112, 116, 117, 118, 119, 120, 124,38125, 126, 127, 133, 134, 135, 136, 137, 138, 141, 142, 143, 145,39148, 149, 150, 151, 152, 154, 156, 157, 158, 159, 161, 164, 165,40166, 167, 173, 174, 175, 180, 181, 182, 183, 184, 188, 189, 190,41191, 194, 197, 198, 199, 205, 206, 207, 208, 210, 212, 213, 214,42215, 216, 219, 220, 221, 222, 223, 224, 226, 229, 230, 231, 237,43238, 239, 240, 244, 245, 246, 247, 248, 252, 253, 254, 255, 257,44260, 261, 262, 263, 265, 269, 270, 271, 276, 277, 278, 279, 280,45284, 285, 286, 287, 291, 293, 294, 295, 299, 301, 302, 303, 306,46308, 309, 310, 311, 312, 313, 316, 317, 318, 319, 320, 323, 325,47326, 327, 330, 333, 334, 335, 336, 340, 341, 342, 343, 344, 348,48349, 350, 351, 352, 353, 357, 358, 359, 365, 366, 367, 368, 369,49371, 372, 373, 374, 375, 376, 380, 381, 382, 383, 384, 386, 389,50390, 391, 395, 397, 398, 399, 404, 405, 406, 407, 408, 410, 412,51413, 414, 415, 421, 422, 423, 426, 429, 430, 431, 434, 436, 437,52438, 439, 440, 442, 444, 445, 446, 447, 448, 453, 454, 455, 457,53461, 462, 463, 464, 465, 468, 469, 470, 471, 472, 476, 477, 478,54479, 480, 485, 486, 487, 493, 494, 495, 496, \ldots,551974, 1975, 1976, 1980, 1981, 1982, 1983, 1984, 1989, 1990, 1991, 1995, 1997, 1998,561999, 2000, 2004, 2005, 2006, 2007, 2008, 2009,\ldots }5758\tableofcontents5960\newpage61\noindent{\bf Goals:}62\begin{itemize}63\item Learn about a major open problem in number64theory.65\item Learn to use \sage{} to draw plots and do66computations.67\item Learn about elliptic curves: groups, public-key68cryptography, the BSD conjecture.69\end{itemize}707172\section{Rational Right Triangles}73\begin{enumerate}74\item Statement of the congruent number problem.75\item Explain what ``enumerate means''.76\item Explain how to enumerate all right triangles with integer side77lengths -- Pythagorean triples: draw graph of circle; draw line;78find other point of intersection; write it as $(x,y)$ with79$x,y$ in terms of $t$.80\item SAGE tutorial:81\begin{enumerate}82\item What is SAGE?83\item SAGE website.84\item SAGE notebook: everyone create a worksheet.85\end{enumerate}86\end{enumerate}87\begin{itemize}88\item \computation89\begin{itemize}90\item Computer lab orientation.91\item Introduction to \sage.92\item Write a program to enumerate rational numbers (make table).93\item Write a program to enumerate Pythagorean triples (make table).94\item Write a program that enumerates rational right95triangles (make table).96\item Write a program that enumerates congruent numbers (make table).97\item Draw plots of numerous rational right triangles (use the {\tt polygon}98command in \sage).99\end{itemize}100\item \theory{}101\begin{itemize}102\item Give a way to enumerate all rational numbers.103\item Give a way to enumerate all rational right triangles.104\item Prove that $n$ is a congruent number if and only if $nk^2$ is105a congruent number for any positive integer $k$.106\item Give a way to enumerate all congruent numbers.107I.e., a procedure that outputs only congruent numbers and108will eventually output any given congruent number.109\item Give an explicit parametrization of all rational solutions110$(x,y)$ to the equation $5x^2 - y^2 = 4$.111\item Give an example of an equation $ax^2 + by^2=1$ with112$a,b\in\Q$ and $a,b>0$ that has no rational solutions $(x,y)$.113\end{itemize}114115\item \research{}116\begin{itemize}117\item Generalize the enumeration method from above to118a method to find all rational solutions to any equation119$ax^2+by^2 = c$, when you're given one solution $P=(x,y)$.120\item Use the internet to try to figure out what the ``local-to-global121principle for binary quadratic forms'' is. Give examples that122illustrate it.123\item {\bf\red Open problem:} Consider an equation $y^2 = f(x)$ with $f$ a124polynomial of degree $5$.125It is a very deep theorem (of Fields Medalist Gerd Faltings) that126there are only finitely many rational solutions $(x,y)\in\Q^2$127of $y^2 = f(x)$. It is an open problem to give an algorithm that128takes as input $f$ and outputs all the solutions to $y^2=f(x)$. This129is currently a very active area of research.130131\end{itemize}132133\end{itemize}134135\section{Congruent Numbers and Elliptic Curves}136Today's workshop is about the connection between congruent137numbers and elliptic curves.138\begin{enumerate}139\item Daily crashing of the SAGE Notebook.140\item The Simuw SAGE Notebooks: login/password, graphics, tab completion,141using mathematica/maple/etc from it.142\item Why are they called ``congruent numbers''? Connection between143congruent numbers and ``congruences'' modulo $n$.144\item 10-minute break.145\item Definition of elliptic curve.146\item Connection between congruent numbers and elliptic curves.147\end{enumerate}148149\begin{itemize}150\item \computation151\begin{itemize}152\item Find the point on an elliptic curve corresponding153to the $(3,4,5)$-triangle.154\item Find the point on an elliptic curve corresponding155to a rational right triangle with area $2006$.156\item Download a table from workshop website of the congruent157numbers up to $1000$, and look for patterns, e.g., reduce the158congruent numbers modulo $8$, etc., and see if you notice159anything.160\item Find a rational number $x$ such that $x-6, x, x+6$ are all perfect squares.161\item Find a rational number $x$ such that $x-2006, x, x+2006$ are all perfect squares.162\item Let $n$ be the year you were born. Is it possible to163find a rational number $x$ such that $x-n, x, x+n$ are all perfect164squares?165%Write a function (using a computer) that takes as input a166% congruent number $n$ and outputs three rational numbers167% $a,b,c$ such that $a,b,c$ are all squares of rational168% numbers, and $b = a+n$, $c = b+n$, i.e., $a,b,c$ are169% ``congruent modulo~$n$''.170\end{itemize}171\item \theory{}172\begin{itemize}173\item Prove that if $n$ is a congruent number then there exists a174rational number $x$ such that175$x-n$, $x$, and $x+n$ are all perfect squares of rational numbers.176177{\small [[Hint: Let $X<Y<Z$ be sides of a rational right178triangle with area $n$. Let $x = (Z/2)^2$.]]}179\item Suppose $n$ is an integer and there exists a rational180number $x$ such that $n-x$, $n$, and $n+x$ are all perfect squares.181Prove that $n$ is a congruent number.182{\small [[Hint: from Koblitz's book (see page 4 of scan on website).183Let $X = \sqrt{x+n} - \sqrt{x-n}$,184$Y = \sqrt{x+n} + \sqrt{x-n}$,185$Z = 2\sqrt{x}$. Then $X,Y,Z$ are the sides of a right186triangle and are all rational, and the triangle has187area $n$.]]}188189\item Think about problems with a similar feel:190\begin{enumerate}191\item Which integers are the192area of a square with rational side lengths?193\item Which integers are the194perimeter of a square with rational side lengths?195\item Which integers are the196area of a rectangle with rational side lengths?197\end{enumerate}198\item199Let~$n$ be a rational number. Prove that there is a bijection between200$$201A = \left\{(a,b,c) \in \Q^3 \,:\, \frac{ab}{2} = n,\, a^2 + b^2 = c^2\right\}202$$203and204$$205B = \left\{(x,y) \in \Q^2 \,:\, y^2 = x^3 - n^2 x, \,\,\text{\rm with } y \neq 0\right\}206$$207given explicitly by the maps208$$209f(a,b,c) = \left(-\frac{nb}{a+c},\,\, \frac{2n^2}{a+c}\right)210$$211and212$$213g(x,y) = \left(\frac{n^2-x^2}{y},\,\,214-\frac{2xn}{y},\,\, \frac{n^2+x^2}{y}\right).215$$216217%\item Find a linear change of variables that gives218%a one-to-one correspondence between points on219%$ny^2 = x^3 + ax^2 +220221\end{itemize}222\item \research{}223\begin{itemize}224\item Try to say something about which integers are the perimeter of a225right triangle with rational side lengths. Try to convert this226question to a question about solutions to equations.227\item Be creative and come up with similar problems, e.g., which228integers are the area of an equilateral triangle with rational side229lengths, etc., some very hard, and convert each to a diophantine230equation.231\item Go to232\begin{verbatim}233http://www.msri.org/publications/ln/msri/2000/introant/234yui/1/index.html235\end{verbatim}236and read about another difficult generalization237of the congruent number problem (this was a talk at a serious238professional research conference, so don't be annoyed if239you don't understand much of it).240\end{itemize}241\end{itemize}242243\begin{center}244%\includegraphics[width=1.1\textwidth, height=0.5\textheight]{graphics/elliptic_curves.png}245\mbox{\hspace{-8.5em}\includegraphics[bb=0 0 500 500]{graphics/elliptic_curves.png}}246\end{center}247For fun -- the above are a bunch of elliptic curves, along248with their {\bf ``Cremona labels''}.249250\newpage251252\section{Congruent Numbers and Elliptic Curves: II}253\begin{enumerate}254\item {\bf\blue The Bijection Revisited Conceptually:} (75 minutes)255\begin{enumerate}256\item (2 minute) Definition of {\em congruent number}.257\item (2 minute) Definition of {\em elliptic curve}.258\item (40 minutes) {\em Bijection} between points and congruent triangles: revisited.259In particular, here is a {\red conceptual way} to think about it.260The set of rational right triangles with area $n$ is261the same as the set of simultaneous solutions to the262system of equations263$$264a^2 + b^2 = c^2, \qquad \frac{ab}{2} = n.265$$266This is the intersection of two quadratic surfaces in $3$-space,267hence a curve. That curve turns out, after an appropriate268change of variables, to be the elliptic curve $y^2 = x^3 - n^2 x$.269Exercise: ...6 steps... (Solution presentation: 30 minute).270\end{enumerate}271272\item {\bf\blue Break:} (10 minute).273274\item {\bf\blue Perimeter:} (15 minute) Discuss the problem of which integers are the275perimeter of a right triangle with rational side lengths.276Again, the set of such triangles for a given $m$ is the277set of simultaneous solutions to 2 equations:278$$279a^2 + b^2 = c^2, \qquad a+b+c = m.280$$281This is the intersection of a quadratic surface and a plane,282hence a quadratic curve.283(Exercise -- 15 minutes trying284this further; presentation of solution.)285286%\item {\bf\blue Graphing Elliptic Curves} (20 minutes):287%Show how to use SAGE to define and graph elliptic curves.288%(Exercise -- experiment for 20 minutes doing this; presentations.)289290\item {\bf\blue Generating New Points on Elliptic Curves from Other Points}291(30 minutes):292Explain how it works. Show how to use SAGE to do it.293(Exercise -- 30 minutes doing this (and getting new triangles); presentations.)294\end{enumerate}295296\begin{itemize}297\item \computation298299\begin{itemize}300\item Find a triangle with perimeter $6$. Hint: rescale301the $3,4,5$ triangle. How does rescaling change the perimeter?302303\item Find four distinct right triangles with area $6$.304305% \item Draw graphs using SAGE of the set of real solutions to several306% elliptic curve equations, e.g., $y^2=x^3+1$, $y^2=x^3-3x+1$, and307% $y^2=x^3-x$.308%\begin{verbatim}309%sage: E = EllipticCurve([-3, 1])310%sage: print E311%Elliptic Curve defined by y^2 = x^3 - 3*x +1 over Rational Field312%sage: show(plot(E))313%\end{verbatim}314315\item Let $E$ be the elliptic curve defined by316$y^2 = x^3 - 36x$,317and let $P=$318Compute $P, 2P, 3P, 4P$319by enter $E$ and $P$ into \sage{} and compute the given sums.320Trying computing lots of other points too.321\begin{verbatim}322sage: E = EllipticCurve([-36,0])323sage: P = E([...])324sage: 2*P325\end{verbatim}326\end{itemize}327328\item \theory{}329\begin{itemize}330\item Fix an integer $n$. Show that the rational right triangles331with area $n$ are in bijection332with the solutions to $y^2=x^3-n^2x$ with $y\neq 0$ as follows:333\begin{enumerate}334\item Think purely conceptually (don't write anything down!):335\begin{enumerate}336\item Imagine the surface337$$338a^2 + b^2 = c^2339$$ in three-dimensional space.340\item Next imagine the surface341$$342\frac{ab}{2} = n343$$ in three-dimensional space.344\item Finally, imagine the intersection of those two surfaces.345You should be visualizing a curve in three dimensional space.346\end{enumerate}347348\item Solve for $a$ in the equation $ab/2 = n$ and substitute349it into $a^2 + b^2 = c^2$ to obtain an equation of the curve350you visualized in three space in the previous problem.351You should be able to put this curve in the form352$$3534n^2 + X^4 = Y^2.354$$355(You'll have to let $X$ and $Y$ equal something involving356$a$ and $b$.)357\item Replace $X$ by $y_1$ and $Y$ by $x_1+y_1^2$ in the358equation for your curve. Simplify and get another curve359(but in the variables $x_1$ and $y_1$):360$$3614n^2 = x_1^2 + 2 y_1^2 x_1362$$363You should be able to do all this by hand. But if you want364to use a computer, here's an example of how in SAGE:365\begin{verbatim}366sage: X = gp('X'); Y = gp('Y'); x_1 = gp('x_1')367sage: y_1 = gp('y_1'); n = gp('n')368sage: print (Y^2).subst(Y,x_1+y_1^2).subst(X, y_1)369sage: print (4*n^2 + X^4).subst(Y,x_1+y_1^2).subst(X, y_1)370x_1^2 + 2*y_1^2*x_1 + y_1^4371y_1^4 + 4*n^2372\end{verbatim}373(In SAGE the command {\tt gp('stuff')} makes a formal variable,374and {\tt subst} allows you to do formal substitutions.)375\item Multiply both sides of the equation you obtain by $x_1$,376then replace $x_1$ by $x_2$ and $y_1$ by $y_2/x_2$, to obtain:377$$3784n^2 x_2 = x_2^3 + 2y_2^2.379$$380381\item Do a few additional manipulations to finally obtain382the equation383$$384y^2 = x^3 - n^2x.385$$386\item If you combine everything you've done so far you get a bijection387from yesterday (you do not have to show this). Moreover, you can388now go back and forth between solutions to $ y^2 = x^3 - n^2x $ and389rational right triangles with area $n$. For example, try this with390$n=6$.391\begin{enumerate}392\item Show that the point on the cubic $y^2 = x^3 - 36x$393that corresponds to the $3,4,5$394triangle is $(-3,9)$.395\item Use \sage{} to find another point $Q$ on $y^2 = x^3 - 36x$.396\item Find the triangle corresponding to $Q$. Verify that it397really does have area $6$.398399\end{enumerate}400\end{enumerate}401402\end{itemize}403404\item \research{}405\begin{itemize}406\item Say something about407perimeters of rational right triangles. Convert this question to408a question about solutions to some equation (as bove). Solve this other409equation. Give a systematic way to enumerate all rational right410triangles with given perimeter.411\end{itemize}412413% \begin{itemize}414% \item Let $F(x,y)$ be a polynomial in two variables.415% We call each of the summands $x^i y^j$ appearing in $F$416% a {\em monomial}, and say it has degree $i+j$. The {\em degree} of417% $F$ is the largest degree of any monomial appear in $F$.418% The {\em homogenization} $G$ of $F$ is the polynomial in $x,y,z$419% got by multiplying each monomial appearing in $F$ by the power of $z$420% so that the degree of every monomial in $G$ is the same as the degree421% of $F$, e.g., the homogenization of $F = x^3 - 3 y^2 + 17x$ is422% $G = x^3 -3 y^2z + 17 xz^2$.423424% \begin{enumerate}425% \item What is the degree of $x^3 + y^3 +1$? What is the426% degree of $x^3y^2 + xy - y^5$? What is the degree of $x^2y^2 + x^3 + 1$?427% \item What is the homogenization of $y^2 = x^3 - x$?428% What is the homogenization of $x^2y^2 + x^3 + 1$?429% What is the homogenization of $y^2 + y = x^3 + x^2 - 2x$?430% What is the homogenization of $y^2 = x^3 $?431%\end{enumerate}432% \end{itemize}433% \item \research{}434% \begin{itemize}435% \item "Rank" of elliptic curves (average, maximal)436% \item What about the points with $x=0$?437% \item What about when cubic has a double root438% (multiplicative or additive group).439% \end{itemize}440\end{itemize}441442443444445446\newpage447\section{Elliptic Curve Groups}448\begin{enumerate}449\item (15 minutes) Presentation -- Perimeters of right triangles?450Patterns in congruent numbers modulo~$8$?451\item (30 minutes) Definition of a {\blue \em group}.452\begin{definition}453An {\red \bf abelian group}454is a set $X$ equipped with a binary operation $+$455and an element $0\in X$ such that for all $a,b,c \in X$,456\begin{enumerate}457\item (closure) $a+b \in X$,458\item (identity) $0 + a = a + 0 = a$,459\item (associativity) $a + (b + c) = (a + b) + c$,460\item (inverses) for every $a$ in $X$ there is $d$ such that $a+d = 0$,461\item (commutativity) $a + b = b + a$.462\end{enumerate}463\end{definition}464465{\bf Examples:}466\begin{enumerate}467\item The {\red\bf integers} $\Z = \{0,-1,1,-2,2,-3,3,\ldots\}$ under addition.468\item The {\red\bf rational numbers} $\Q$ under addition.469\item The {\red\bf integers} $\{0,1,\ldots, n-1\}$ under {\red\bf addition470modulo $n$}.471\item Let $p$ be a prime. The {\red\bf integers} $\{1,\ldots, p-1\}$472under {\red\bf multiplication modulo $p$}.473This is called {\red $\F_p^*$}.474\end{enumerate}475476477\item (15 minutes) Experiment with some abelian groups in \sage.478479\item (10 minutes) Break.480481\newpage482\item (20 minutes) Definition of elliptic curve groups.483484\begin{definition}485Fix integers $a$ and $b$.486Let {\red $E(\Q)$} be the set of solutions to $y^2 = x^3 + a x + b$487along with one ``extra point'' which we call $\cO$ which is488the additive $0$ element. This is an489abelian group (note: the associative law takes a {\em lot} of work to prove!).490\end{definition}491492493\item (30 minutes) Participants: Graph elliptic curves.494Then {\bf\blue derive an algebraic formula} (by hand) for the495group operation.496497\item (15 minutes) Elliptic curves modulo $p$.498Fix integers $a$ and $b$ and a prime $p$.499Let {\red $E(\F_p)$} be the set of solutions to $y^2 \con x^3 + a x + b\pmod{p}$500with $0\leq x < p$ and $0\leq y < p$ along with a formal extra501point $\cO$. This group is central in both cryptography (in making502{\em and} cracking cryptosystems) and the Birch and Swinnerton-Dyer503conjecture! I will explain how in both cases next week.504505\item (15 minutes) Participants:506Graph and compute with some elliptic curves modulo $p$.507508\end{enumerate}509510\newpage511\subsection{Elliptic Curves over $\Q$}512\begin{itemize}513\item \computation514\begin{itemize}515\item Play around with each of the above groups in \sage.516Here are examples of how to compute with each of the517groups listed above in \sage{} to get you started.518Be creative and experiment!519\begin{verbatim}520sage: ZZ521Integer Ring522sage: a = ZZ(5); b = ZZ(7); a+b52312524525sage: QQ526Rational Field527sage: QQ(3/4) + QQ(2/3)52817/12529530sage: R = IntegerModRing(12)531sage: print R532Ring of integers modulo 12533sage: R(7) + R(8)5343535536sage: R = FiniteField(7)537sage: print R538Finite Field of size 7539sage: R(4)*R(5)5406541\end{verbatim}542543\item Compute with elliptic curves over $\Q$. Here544is an example to get you started.545\begin{verbatim}546sage: E = EllipticCurve([-36,0])547sage: E548Elliptic Curve defined by y^2 = x^3 - 36*x over Rational Field549sage: P = E([-3,9]) # or use E.gens(proof=False)550sage: P + P551(25/4 : -35/8 : 1)552\end{verbatim}553554555\item Draw some graphs of elliptic curves (using the new program556I just wrote!). Here557is an example to get you started:558\begin{verbatim}559sage: E = EllipticCurve([-36,0])560sage: P = plot(E,rgbcolor=(0,0,1))561sage: pnt = E([-3,9])562sage: pnt2 = 2*pnt563sage: c1 = point(pnt, pointsize=100)564sage: c2 = point(pnt2, rgbcolor=(1,0,0), pointsize=100)565sage: show(P + c1 + c2)566\end{verbatim}567%\item568%Write a program that outputs 20 rational right triangles569%with area $6$. Plot some of these.570\end{itemize}571\item \theory{}572\begin{itemize}573%\item The group has a point $(x,y)$ with $y\neq 0$ if and only if $n$ is574%a congruent number.575%\item Geometric proof that composition law is associative576%[for people who love geometry -- [[copy the argument from Silverman-Tate577%here]]]578\item579Let $E$ be an elliptic curve580given by an equation $y^2=x^3+ax+b$.581Prove that the following steps can be used to compute582$+$ on $E$: Given $P_1, P_2$,583this algorithm computes the third point $R=P_1+P_2$.584\begin{enumerate}585\item{}[Is $P_i=\O$?] If $P_1=\O$ set $R=P_2$ or if $P_2=\O$ set $R=P_1$586and terminate. Otherwise write $(x_i,y_i)=P_i$.587\item{}[Negatives] If $x_1 = x_2$ and $y_1 = -y_2$, set $R=\O$ and terminate.588\item{}[Compute $\lambda$]\label{alg:grouplaw_3}589Set $\ds \lambda = \begin{cases}590(3x_1^2+a)/(2y_1) & \text{if }P_1 = P_2,\\591(y_1-y_2)/(x_1-x_2) & \text{otherwise.}592\end{cases}$\\593\item{}[Compute Sum]\label{alg:grouplaw_4} Then594$R = \ds \left(\lambda^2 -x_1 - x_2, -\lambda x_3 - \nu\right)$,595where $\nu = y_1 - \lambda x_1$ and $x_3=\lambda^2 -x_1 - x_2$596is the $x$-coordinate of $R$.597\end{enumerate}598\end{itemize}599\item \research{}600\begin{itemize}601\item Using the Internet find two web pages that define abelian602groups. Understand the definitions (perhaps by copying them down603onto a piece of paper). Do they agree with the definition604that I gave above?605%\item It is true that if $n$ is a congruent number, there are infinitely606% many distinct rational right triangles with area $n$.607\end{itemize}608609\end{itemize}610611612\subsection{Elliptic Curves Modulo $p$}613Definition, arithmetic, point enumeration,614elliptic curve cryptography (discrete log problem; diffie-hellman).615616\begin{itemize}617\item \computation618\begin{itemize}619\item Compute with elliptic curves modulo a prime $p$. Here620is an example to get you started.621\begin{verbatim}622sage: E = EllipticCurve(FiniteField(43), [-36,0])623sage: E624Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 43625sage: P = E([-3,9])626sage: P + P627(17 : 1 : 1)628\end{verbatim}629\item Graph some elliptic curves modulo $p$:630\begin{verbatim}631sage: E = EllipticCurve(FiniteField(13), [-36,0])632sage: P = plot(E,rgbcolor=(0,0,1),pointsize=100)633sage: P.show(dpi=200)634\end{verbatim}635\end{itemize}636637% \begin{itemize} \item draw graphs of the groups (set of all points)638% \item compute group law explicitly (and graph the cycle get639% by adding one point over and over).640% \item number of points over $\F_p$ for lots of $p$ (the Sato-Tate641% distribution).642% \item Hasse bound (proof beyond scope, but statement is easy, and numerical643% evidence is too).644% \end{itemize}645\item \theory{}646\begin{itemize}647\item Given $P$ and a positive integer $n$, it is fairly648straightforward to compute $nP = P + P + \cdots + P$. Given649$P$ and $Q$ where you know that $Q=nP$ for some $n$ (even650though you don't know $n!$), invent a way to find $n$ (it651doesn't have to be fast).652\end{itemize}653% \item \research{}654% \begin{itemize}655% \item Discrete log problem.656% \item Diffie-hellman and El Gammal cryptosystem -- see Sandor's talks later.657% \end{itemize}658\end{itemize}659660661\newpage662\section{The Birch and Swinnerton-Dyer Conjecture (Monday)}663\begin{center}664\includegraphics[bb=0 0 550 300 height=13em, width=25em]{graphics/swinnerton_dyer-count.png}665\end{center}666\begin{enumerate}667\item (15 minutes) Congruent number problem; connected668to elliptic curves; we need to understand when elliptic curves669have points on them.670\item (15 minutes) Daily crashing of the SAGE Notebook -- some671improvements I made over the weekend: computing \code{E.points()}672for $E$ an elliptic curve modulo~$p$ is now very fast; the Notebook673interface is generally more robust and much easier to interrupt;674\code{foo??} gives source code even for functions you enter or in675cong.sage if you do \code{attach cong.sage}; can write, e.g.,676\code{plot(..., hue=...)} instead of \code{plot(...,677rgbcolor=hue(...))}. So please, right now, {\red try hard to678``crash'' your personal SAGE Notebook}, i.e., get it in an679unresponsive state. Don't worry, I can easily restart all of them.680\item {\blue\bf The Conjecture}.681The Birch and Swinnerton-Dyer conjecture was made in the 1960s682based on numerical computations carried out on EDSAC:683\includegraphics[bb=0 0 300 180]{graphics/edsac.png}684685Let $n$ be a positive square-free integer. This means686that no perfect square divides $n$.687Let $E_n$ be the elliptic curve $$E_n: \quad y^2 = x^3 - n^2x.$$688If $n$ is odd, let $N = 32n^2$, and if $n$689is even, let $N=16n^2$. The number $N$ is called690the {\blue\em conductor of $E_n$}.691692For any prime $p\nmid 2n$,693let694$$695a_p = p + 1 - \#E_n(\F_p),696$$697where $\#E_n(\F_p)$ is the number of points on the elliptic curve698$E_n$ viewed modulo $p$.699If $p\mid 2n$, let $a_p = 0$.700If $m, r$ are coprime integers, let $a_{mr} = a_m a_r$.701If $p\nmid 2n$ let $a_{p^r} = a_{p^{r-1}} a_p - p a_{p^{r-2}}$,702and if $p\mid 2n$ let $a_{p^r} = 0$.703Finally, let704$$705L(E_n,1) = \begin{cases}7060 & \text{if $n\con 5,6,7\pmod{8}$}\\707\ds 2 \cdot \sum_{k=1}^{\infty} \frac{a_k}{k} \cdot e^{-2\pi k/\sqrt{N}} & \text{otherwise}.708\end{cases}709$$710\begin{conjecture}[Birch and Swinnerton-Dyer]\mbox{}\vspace{-4ex}\\711\begin{center}712We have $L(E_n,1) = 0$ if and only if $E_n(\Q)$ is infinite.713\end{center}714\end{conjecture}715(Stated in a special cases.)716717This is a {\em\red major open problem} in number theory. {\em If718I don't solve this problem, I hope one of you does!}719720\begin{proof}[Heuristic ``Proof'']721(This is a {\em\red\bf fake} ``proof''.)722If $E_n(\Q)$ is infinite then the numbers $\#E_n(\F_p)$ will723tend to be {\em\large big}, since you get lots of elements724of $E_n(\F_p)$ by reducing the elements of $E_n(\Q)$725modulo $p$. Thus $a_p = p+1 - \#E_n(\F_p)$ will tend726to be {\em small}. One can prove that $L(E_n,1)\geq 0$,727so if the $a_p$ are small, that will ``cause'' the728sum that defines $L(E_n,1)$ to be small, i.e., $0$.729Conversely if $L(E_n,1)=0$, then the $E_n(\F_p)$ are big,730and the points have to come from somewhere so $E_n(\Q)$731is big.732\end{proof}733734\begin{theorem}[Kolyvagin et al.]735If $E_n(\Q)$ is infinite then $L(E_n,1)=0$.736\end{theorem}737This is one direction in the conjecture, and the738proof is {\em very very difficult}. Put another way,739this theorem says that if $L(E_n,1)\neq 0$, then $E_n(\Q)$ is finite.740741742As the notation suggests, $L(E_n,1)$ is the value743of a function at $1$. I will not define the general744function, but here are some plots of $L(E_n,s)$ for745various $n$:746\par747748{\hspace{-6em}\noindent$n=1$\includegraphics[bb=0 0 180 150]{graphics/lser1.png}749$n=6$\includegraphics[bb=0 0 180 150]{graphics/lser6.png}}750751{\hspace{-6em}$n=34$\includegraphics[bb=0 0 180 150]{graphics/lser34.png}752$n=4199$\includegraphics[bb=0 0 180 150]{graphics/lser4199.png}}753754I made them using code like755\begin{verbatim}756E = EllipticCurve([-6^2,0])757L = E.Lseries_dokchitser()758P = plot(L,0.5,1.5, plot_points=50, plot_division=50,759rgbcolor=(0,0,1), thickness=2)760\end{verbatim}761762763\item Participants -- do the following for $n=1$ and $n=34$:764\begin{enumerate}765\item Write down $E_n$.766\item Find the conductor $N$ of $E_n$.767\item Compute (by hand/with computer) $a_1, a_2, a_3, a_4$, and $a_5$.768Check your answer with \sage (use {\tt E.an(m)} to compute $a_m$).769The point here is to spend some time understanding the770definition of $a_m$.771\item Compute the first $5$ terms in the sum772that defines $L(E_n,1)$.773774(You should find that for775$n=34$ we have $L(E_{34},1)=0$, whereas for $n=1$ we776have $L(E_{1},1)\neq 0$.)777\begin{verbatim}778sage: E = EllipticCurve([-1^2,0])779sage: E.Lseries(1)7800.65551438857302990781782sage: E = EllipticCurve([-34^2,0])783sage: E.Lseries(1)784-0.0000000000000000... (the nonzeros at the end are just errors/noise)785\end{verbatim}786787\item The following SAGE program can be used to compute the788sum that defines $L(E_n,1)$ using any number of terms.789\begin{verbatim}790def L(n, prec):791E = EllipticCurve([-n^2,0])792v = E.anlist(prec)793N = E.conductor()794sqrtN = sqrt(N)795lval = 2*sum(v[n]/n*exp(-2*pi*n/sqrtN) for n in range(1,prec))796return lval797\end{verbatim}798Note: This function is in {\tt cong.sage}. Just type799\code{attach cong.sage} if you haven't already and it800will magically be available. Then you can enter801\code{L?} for help and \code{L??} for source code.802\end{enumerate}803804805806\item Participants -- Prove using SAGE calculations and the BSD807conjecture that none of $1,2,3,4$ are congruent numbers.808\item Participants -- Try to find patterns, any at all,809in the numbers $$p+1-\#E_n(\F_p)$$810for the congruent number curves $y^2 = x^3 - n^2x$.811E.g., fix $n=1$ and compute these numbers for812primes up to some bound:813\begin{verbatim}814E = EllipticCurve([-1,0])815for p in primes(2,100):816print p, E.ap(p)817\end{verbatim}818\end{enumerate}819\begin{itemize}820\item \computation821\begin{itemize}822\item This \sage code823draws the plot below. Try different curves, ranges of primes, etc.824\begin{verbatim}825n = 6826def pl(p):827return plot(EllipticCurve(GF(p),[-n^2,0]), rgbcolor=hue(0.7))828829P = [pl(p) for p in primes(5,100) if n%p != 0]830Q = [[P[4*i+j] for j in range(4)] for i in range(len(P)/4)]831show(graphics_array(Q))832# show(graphics_array(Q), axes=False) # if you don't want axes833\end{verbatim}834{\hspace{-10.5em}\includegraphics[bb=0 0 450 350]{graphics/points_mod_p.png}}835836%\item Verify using \sage that $N_p = p+1$ for $p\con 3\pmod{4}$ with837%$p<1000$, where $N_p$ is the number of points on $y^2 = x^3 - x$838%over $\F_p$. (Helpful hint to get you going below.)839%\begin{verbatim}840%for p in primes(20):841% print p, E.Np(p)842%\end{verbatim}843844\item Make a table of values $L(E_n,1)$ for each integer $n< 50$.845How does this compare to the table of congruent numbers $n<50$.846[Here's how to {\em approximately} compute $L(E,1)$ in SAGE:]847848\item In this problem $n$ {\em always} denotes a squarefree849positive integer $n$ (i.e., no perfect squares divide $n$).850\begin{enumerate}851\item If $n\con 5,6,7\pmod{8}$ then does852the Birch and Swinnerton-Dyer conjecture imply that853$n$ is a congruent number?854\item Are there {\em any} integers $n \con 3\pmod{8}$ with $n$ a855congruent number?856\begin{verbatim}857EllipticCurve([-1,0]).Lseries(1)858\end{verbatim}859\end{enumerate}860\end{itemize}861862\item \theory{}863\begin{itemize}864%\item Prove that $N_p = p+1$ for $p\con 3\pmod{4}$.865\item What is the relationship between the866$a_p$ for $E_1$ and $E_6$? Make a conjecture based867on numerical evidence. Note: you can compute868$a_p$ using {\tt E.ap(p)}, e.g.,869\begin{verbatim}870E = EllipticCurve([-1,0])871for p in primes(10):872print p, E.ap(p)873\end{verbatim}874Can you say anything about the relation between the875$a_p$ for $E_1$ and for $E_n$ for general $n$?876\end{itemize}877878\item \research{}879\begin{itemize}880\item Find Andrew Wiles's paper on the Birch and Swinnerton-Dyer881conjecture at the Clay Math Institute web site882\url{http://www.claymath.org/millennium/} and read as much of it883as you can. One of their pages says:884\begin{quote}885``Mathematicians have always been fascinated by the problem of describing all solutions in whole numbers $x,y,z$ to algebraic equations like886$$887x^2 + y^2 = z^2.888$$889890Euclid gave the complete solution for that equation, but for more891complicated equations this becomes extremely difficult. Indeed, in8921970 Yu. V. Matiyasevich showed that Hilbert's tenth problem is893unsolvable, i.e., there is no general method for determining when such894equations have a solution in whole numbers. But in special cases one895can hope to say something. When the solutions are the points of an896abelian variety, the Birch and Swinnerton-Dyer conjecture asserts that897the size of the group of rational points is related to the behavior of898an associated zeta function $L(s)$ near the point $s=1$. In899particular {\em\blue this amazing conjecture asserts that if $L(1)$ is equal900to $0$, then there are an infinite number of rational points901(solutions), and conversely, if $L(1)$ is not equal to 0, then902there is only a finite number of such points.}''903904\end{quote}905906\item Noam Elkies web page907\url{http://www.math.harvard.edu/\~{ }elkies/compnt.html}908has the most extensive data I've seen about congruent numbers.909Check it out!910911\item EDSAC -- search for information online about the912EDSAC computer.913\end{itemize}914\end{itemize}915916\newpage917\section{Square Triangles and Fermat's Last Theorem (Wed morning)}918919The numbers $1$, $2$, $3$, and $4$ are not congruent numbers. In920particular, $1$ is not. I.e., there is not rational right triangle921whose area is a perfect square, i.e., there are no ``square922triangles''.923924\begin{enumerate}925\item (60 minutes) Watch the Fermat's Last Theorem movie.926\item (10 minutes) Move to computer lab / break.927\item (10 minutes) Recall that we ``know'' $1$ is not a congruent928number from Monday, since $L(E_1, 1) = 0.65551\ldots \neq 0$. But that929uses a deep theorem (the proof by Kolyvagin of one direction930of the Birch and Swinnerton-Dyer conjecture).931\item (70 minutes) Prove Fermat's Last Theorem for $n=4$, and use this932to deduce that $1$ is not a congruent number.933\end{enumerate}934935\begin{itemize}936\item \computation937\begin{itemize}938\item Via a direct computer search, show there are no right triangles939with area $1$ and rational side lengths $(a,b,c)$ (with $c$ the940hypotenuse) with the number of digits of the numerators and941denominators of $a$, $b$, $c$ all $<100$ in absolute value.942\item Look for solutions to $y^2=x^3-x$ with both $x,y$ rational and943$y\neq 0$. Fail to find any.944\end{itemize}945\item \theory{} You {\em\red definitely} want to work together on these946problems, even possibly dividing up into groups and assigning parts947to different groups, and also having people search online for help948(which is allowed). Make solving all these nicely a community949effort. [Credit: This sequence of problems was originally written950by the Baur Bektemirov (the first ever winner951of the International Math Olympiad gold medal from Kazakhstan),952while he was a freshman at Harvard working with me.]953\begin{enumerate}954\item\label{ex:pythag} Suppose $a$, $b$, $c$ are relatively prime955integers with $a^2+b^2=c^2$. Then there exist integers $x$ and $y$956with $x>y$ such that $c=x^2+y^2$ and either $a=x^2-y^2$, $b=2xy$ or957$a=2xy$, $b=x^2-y^2$. Hint: Recall what we did on day 1958where we parametrized Pythagorean triples $a,b,c$:959\begin{center}960\mbox{\hspace{-8em}\includegraphics[bb=0 0 400 250 width=0.8\textwidth]{graphics/pythag.png}}961\end{center}962963964\item\label{ex:flt4} Fermat's Last Theorem for exponent $4$ asserts965that any solution to the equation $x^4+y^4=z^4$ with $x,y,z\in\Z$966satisfies $xyz=0$. Prove Fermat's Last967Theorem for exponent $4$, as follows.968\begin{enumerate}969\item Show that if the equation $x^2+y^4=z^4$ has no integer970solutions with $xyz\neq 0$, then Fermat's Last Theorem for exponent~$4$971is true. (Note -- the power of $x$ is $2$.)972\item Prove that $x^2+y^4=z^4$ has no integer solutions with $xyz\neq 0$973as follows.974Suppose $n^2+k^4=m^4$ is a solution with $m>0$ minimal amongst975all solutions. Show that there exists a solution with $m$ smaller976using the previous exercise above (consider two cases).977\end{enumerate}978979\item Prove that 1 is not a congruent number by showing that980the cubic curve $y^2=x^3-x$ has no rational solutions981except $(0,\pm 1)$ and $(0,0)$:982\begin{enumerate}983\item Write $y=\frac{p}{q}$ and $x=\frac{r}{s}$, where $p,q,r,s$ are984all positive integers and $\gcd(p,q)=\gcd(r,s)=1$. Prove that $s\mid985q$, so $q=sk$ for some $k\in\Z$.986\item Prove that $s=k^2$, and substitute to see that987$p^2=r^3-rk^4$.988\item Prove that $r$ is a perfect square by supposing989that there is a prime~$\ell$ such that $\ord_{\ell}(r)$ is990odd and analyzing $\ord_{\ell}$ of both sides of991$p^2=r^3-rk^4$.992\item Write $r=m^2$, and substitute to993see that $p^2=m^6-m^2k^4$. Prove that $m\mid p$.994\item Divide through by $m^2$ and deduce a contradiction to the995previous exercise.996\end{enumerate}997998\end{enumerate}999\end{itemize}100010011002\newpage1003\section{An Elementary Criterion (Thursday)}10041005\begin{enumerate}1006\item ($<1$ hour) -- Student presentations: proof of FLT for exponent 4 and1007no square triangles.1008\item (10 minutes) -- break1009\item (30 minutes) -- statement of Tunnell's criterion.1010Let $$\Theta(q) = 1 + 2\sum_{m\geq 1} q^{m^2} =10111 + 2q + 2q^{4} + 2q^{9} + \cdots.$$1012Let1013$$f_1 = \Theta(q)\cdot (2\Theta(q^{32}) - \Theta(q^8))\cdot \Theta(q^2)$$1014and1015$$f_2 = \Theta(q) \cdot (2\Theta(q^{32}) - \Theta(q^8))\cdot \Theta(q^4).$$1016\begin{theorem}[Waldspurger, Tunnell]\label{thm:tunnell}1017Suppose $n$ is a squarefree integer. If $n$ is odd1018then $L(E_n,1)=0$ if and only if the $n$th coefficient1019of $f_1$ is $0$. If $n$ is even then $L(E_n,1)=0$1020if and only if the $\frac{n}{2}$th coefficient of $f_2$ is $0$.1021\end{theorem}1022This is a {\bf\blue very deep theorem}. It allows us to determine1023whether or not $L(E_n,1)=0$.1024The Birch and Swinnerton-Dyer conjecture (which is not1025a theorem) then asserts that $L(E_n,1)=0$ if and only if $n$1026is a congruent number. Thus once enough of the1027Birch and Swinnerton-Dyer conjecture is proved, we'll have1028an elementary way to decide whether or not a (squarefree)1029integer $n$ is a congruent number. Namely,1030if $n$ is odd then (conjecturally) $n$ is a congruent number1031if and only if1032$$\#\left\{x,y,z\in\Z \,:\, 2x^2 + y^2 + 32z^2 = n\right\}1033= \frac{1}{2} \#\left\{x,y,z\in\Z \,:\, 2x^2 + y^2 + 8z^2 = n\right\}.1034$$1035Simiarly,1036if $n$ is even then (conjecturally) $n$ is a congruent number1037if and only if1038$$\#\left\{x,y,z\in\Z \,:\, 4x^2 + y^2 + 32z^2 = \frac{n}{2}\right\}1039= \frac{1}{2} \#\left\{x,y,z\in\Z \,:\, 4x^2 + y^2 + 8z^2 = n\right\}.1040$$104110421043\item (30 minutes) -- exercises with Tunnell's criterion.1044\begin{enumerate}1045\item Come up with a method to explicitly list1046each of the above sets.10471048\item Prove that the elementary criterion (involving cardinality of1049sets) implies that none of $n=1,2,3,4$ are congruent numbers.10501051\item Prove that the elementary criterion (involving cardinality of1052sets) implies that $n=5,6,7$ are congruent numbers. Then find1053a right triangle with area $5$.10541055\item Verify with \sage that Theorem~\ref{thm:tunnell} (appears to)1056hold for $n<20$. Hint: The command1057\begin{verbatim}1058f1, f2 = tunnell_forms(30)1059\end{verbatim}1060computes the $f_1$ and $f_2$ defined above, and e.g., \code{f1[3]}1061returns the coefficient of $q^3$.10621063\item {\bf Question (Nathan Ryan):} Is it possible to decide whether1064or not a prime number $p$ is a (conjectural) congruent number in1065time polynomial in the number of digits of $p$? I.e., if $p$ has a1066hundred digits is there any hope we could tell whether or not $p$ is1067(conjecturally) a congruent number i a reasonable amount of time?1068[[{\bf\red WARNING: This is an unsolved problem, as far as I1069know.}]]1070\end{enumerate}10711072\end{enumerate}1073107410751076\newpage1077\section{Square Triangles Revisited}1078Since there was so much trouble with the proof of Fermat for exponent1079$4$, let's revisit it. First, Fermat's proof:1080\begin{quote}1081``if the area of a rational right triangle were a square, then1082there would also be a smaller one with the same property, and so on,1083which is impossible.''1084\end{quote}1085OK, that wasn't so helpful.1086Anyway, we did everything on Thursday except 2b, i.e.,1087suppose that $n^2 + k^4 = m^4$ is a solution in positive1088integers to the equation $x^2 + y^4 = z^4$ with $m>0$1089minimal among all possible solutions. Show that there is a1090a smaller solution, hence deduce a contradiction.1091\begin{enumerate}1092\item Case 1: If $n$ is even then there exist integers $x,y\geq 0$1093(with $x>y$) such that1094$$n = 2xy\qquad k^2 = x^2 - y^2 \qquad m^2 = x^2 + y^2.$$1095Then1096$$1097(mk)^2 = x^4 - y^4,1098$$1099from which we obtain a smaller solution.11001101\item Case 2: Next assume $n$ is odd. The trick is to proceed as1102above, but to apply exercise 1 again to the Pythagorean triple $m^21103= x^2 + y^2$ and note that various numbers are perfect squares. We1104give full details below.11051106There are integers $x,y$ with $x>y$ such that1107$$n = x^2 - y^2\qquad k^2 = 2xy \qquad m^2 = x^2 + y^2.$$11081109Since $2xy=k^2$ is a perfect square we can write1110either $x=u^2$, $y=2v^2$ or $x=2u^2$, $y=v^2$ for integers1111$u,v$.11121113\begin{enumerate}1114\item Case: We have $x=u^2, y=2v^2$, i.e., $y$ is even and1115$x$ is odd (note that $x$ must be odd if $y$ is even1116since $n=x^2-y^2$ is odd).1117Since $m^2 = x^2 + y^2$ is itself a Pythagorean1118triple with $x$ odd, we can again apply exercise 1 to find coprime1119integers $a,b$ such that1120$$1121x = a^2 - b^2\qquad y = 2ab\qquad z = a^2 + b^2.1122$$1123Then $2v^2 = y = 2ab$, so since $a,b$ are coprime we have1124$a = d^2$, $b=e^2$ for integers $d,e$.1125Since $x=u^2$ and $x=a^2-b^2$, we have1126$$1127u^2 = d^4 - b^4,1128$$1129which yields a smaller solution to $x^2 + y^4 = z^4$.1130\item Case: We have $x=2u^2, y=v^2$, i.e., $y$ is odd and1131$x$ is even (note that $y$ must be odd if $x$ is even1132since $n=x^2-y^2$ is odd).1133Since $m^2 = x^2 + y^2$ is itself a Pythagorean1134triple with $y$ odd, we can again apply exercise 1 to find coprime1135integers $a,b$ such that1136$$1137y = a^2 - b^2\qquad x = 2ab\qquad z = a^2 + b^2.1138$$1139Then $2u^2 = x = 2ab$, so since $a,b$ are coprime and1140have square product we have1141$a = d^2$, $b=e^2$ for integers $d,e$.1142Since $y=v^2$ and $y=a^2-b^2$, we have1143$$1144v^2 = d^4 - b^4,1145$$1146which yields a smaller solution to $x^2 + y^4 = z^4$.11471148\end{enumerate}11491150\end{enumerate}115111521153\newpage1154\section{An Elliptic Curve Cryptography (ECC) Tutorial}1155Elliptic curves are useful far beyond the fact that they shed a huge1156amount of light on the congruent number problem. For example, many1157people (probably you!) use them on a daily basis, since they are used1158to make some of the best public-key cryptosystems (= methods for1159sending secret data).116011611162I think the Wikipedea opening description of Elliptic curve1163cryptography is OK (no comment about the rest of the article):1164\begin{quote}1165Elliptic curve cryptography (ECC) is an approach to public-key1166cryptography based on the algebraic structure of elliptic curves1167over finite fields. The use of elliptic curves in cryptography was1168suggested independently by Neal Koblitz [1] and Victor S. Miller [2]1169in 1985.11701171Elliptic curves are also used in several integer factorization1172algorithms that have applications in cryptography, such as, for1173instance, Lenstra elliptic curve factorization, but this use of1174elliptic curves is not usually referred to as "elliptic curve1175cryptography."11761177[...] As for other popular public key cryptosystems, no mathematical1178proof of difficulty has been published for ECC as of 2006. However,1179the U.S. National Security Agency has endorsed ECC technology by1180including it in its Suite B set of recommended algorithms. Although1181the RSA patent has expired, there are patents in force covering some1182aspects of ECC.1183\end{quote}1184Note: Neal Koblitz is a math professor here at UW. He wrote the book1185on the congruent number problem (I scanned some of it for the1186website). You might see him around this summer, since he's teaching a1187summer school class.1188\begin{center}1189\includegraphics[bb=0 0 75 100]{graphics/koblitz.png}1190\end{center}11911192{\bf \blue Basic Problem:} {\em How can people or computers send1193secret messages to each other without having to send out passwords1194ahead of time? How did mathematicians put the guys with briefcases1195handcuffed to their hands out of business?}11961197Sandor Kovacs will go into great detail about this question in1198his course, and you might view today as a preview of some of what1199he'll do, with the bonus that today you get to try it out on a1200computer. Today I'll just give you the chance to {\em understand and1201play with} one example that addresses this basic problem.12021203\subsection{Elliptic Curves Modulo $p$}1204Let $p$ be a prime number. Consider an equation1205$y^2 = x^3 + ax + b$ with1206$$a,b \in \F_p = \{0,1,\ldots, p-1\} \qquad\text{(integers modulo $p$)}$$1207such that the cubic $x^3 + ax + b$ has distinct roots.1208The group of points on $E$ modulo $p$ is1209$$1210E(\F_p) = \{(x,y)\in \F_p \times \F_p : y^2 = x^3 +ax + b\} \union \{\cO\}.1211$$12121213{\bf Exercise:} Make up several ``random'' elliptic curves over1214various random $\F_p$'s in \sage (so {\em not} related to the1215congruent number problem!). List their points. Plot them. Do a1216little arithmetic with them. Here is some code to get you1217started.\vspace{1ex}12181219\noindent{}Finding a random prime $<1000$:1220\begin{verbatim}1221sage: next_prime(randrange(1000))12221371223\end{verbatim}1224Making up a random curve:1225\begin{verbatim}1226sage: p = 1371227sage: F = FiniteField(p)1228sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])1229sage: print E1230Elliptic Curve defined by y^2 = x^3 + 45*x + 43 over Finite Field of size 1371231\end{verbatim}1232List all points:1233\begin{verbatim}1234sage: E.points()1235[(0 : 1 : 0), (51 : 90 : 1), (57 : 92 : 1), (90 : 34 : 1), ...1236\end{verbatim}1237Make a plot:1238\begin{verbatim}1239sage: show(plot(E, hue=.9))1240\end{verbatim}1241Do some arithmetic:1242\begin{verbatim}1243sage: P = E.points()[1] # first point listed above1244sage: P1245(51 : 90 : 1)1246sage: P + P1247(57 : 92 : 1)1248sage: 10*P1249(131 : 105 : 1)1250sage: 9393*P1251(129 : 26 : 1)1252\end{verbatim}125312541255\subsection{Computing $nQ$ }1256Recall from yesterday that computers can compute $a^m \pmod{n}$ very1257quickly, even if $m$ is {\bf huge}. They do this by writing $n$1258in binary and doing a few squares and multiplies. Likewise,1259we can compute $nQ$ quickly when $Q$ is a point on an elliptic1260curve modulo $p$. Try it out!1261\begin{verbatim}1262sage: p = 1371263sage: F = FiniteField(p)1264sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])1265sage: P = E.random_element()1266sage: print P1267(96 : 94 : 1)12681269sage: time 102000823098320*P1270(86 : 60 : 1)1271CPU time: 0.12 s, Wall time: 0.13 s12721273sage: show(plot(P) + plot(102000823098320*P,rgbcolor=(1,0,0)))1274[[a plot]]1275\end{verbatim}1276Now try with an elliptic curve over a huge field.1277\begin{verbatim}1278sage: p = next_prime(randrange(10^40))1279sage: print p1280sage: F = FiniteField(p)1281sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])1282sage: P = E.random_element()1283sage: print P12845541466958757039311365508431861627631211285(493257625218361211096484901389666856690 :1286286863248034562484128552069228984577311 :12871)1288\end{verbatim}1289Then multiply...1290\begin{verbatim}1291sage: time 909238403284092384209482038402*P1292(151371634043111300277840422027192273952 :1293333732213371771487412281506530764174375 :12941)1295CPU time: 0.20 s, Wall time: 0.21 s1296\end{verbatim}12971298\subsection{Diffie-Hellman -- a way to create a shared secret}1299The Diffie-Hellman key exchange was the first ever public-key1300cryptosystem. We will try it out on a elliptic curve here1301(note: it can also be used directly in $\F_p^* = \{1,\ldots, p-1\}$,1302as you will learn in Sandor's course).13031304Public key cryptography involves three ``people'':1305\begin{itemize}1306\item Person 1 -- traditionally named Alice1307\item Person 2 -- traditionally named Bob1308\item Person 3 -- traditionally called The Adversary1309\end{itemize}13101311\begin{enumerate}1312\item Break up into groups of (at least) 3. Choose at least person to1313be Alice\footnote{Even a guy could be ``Alice'', e.g., there is a1314guy named Alice Cooper from Phoenix, AZ.}, at least one to be1315Bob\footnote{Are there any famous women named Bob?}, and one to be1316the Adversary. Each person should have a computer terminal open to1317their SIMUW SAGE notebook. Open a common SAGE worksheet that all1318three of you can see and use to post messages (by refreshing the1319page). I'll explain how to do this.13201321\item In this exercise Alice and Bob will agree on a secret key1322by sending message {\em in full view} of everybody else. Of course,1323what they do at there computers gets kept secret -- only the messages1324are public (in particular, Adversary should not look at the crypto1325worksheets of Alice and Bob).13261327\item Alice: Choose a random prime $p$ and create a random1328elliptic curve modulo $p$, then choose a random point on this1329elliptic curve.1330\begin{verbatim}1331sage: load cong.sage # defines random_elliptic_curve command1332sage: E = random_elliptic_curve(next_prime(randrange(1000)))1333sage: print E1334Elliptic Curve defined by y^2 = x^3 + 508*x + 42 over Finite Field of size 5771335\end{verbatim}13361337\begin{verbatim}1338sage: P = E.random_element()1339sage: P1340(386 : 331 : 1)1341\end{verbatim}1342Finally, Alice has to tell everybody the random elliptic curve1343and the random point in such a way that Bob can define it1344on his computer. In the above example, just report that1345the prime is $47$, that the curve is \code{EllipticCurve([36,3])},1346and the point is $(5,4)$.13471348\item Bob: Choose a random integer $b$ (up to about $p$ in size)1349and compute $bP$ and tell everyone.1350\begin{verbatim}1351sage: b = randrange(1000); b13525491353\end{verbatim}13541355\begin{verbatim}1356sage: b*P1357(472 : 340 : 1)1358\end{verbatim}13591360Announce $(83,362)$ to the world. But keep b secret.13611362\item Alice: Do the same thing as Bob, but with your own1363integer $a$.1364\begin{verbatim}1365sage: a = randrange(1000); a136677913671368sage: a*P1369(54 : 426 : 1)1370\end{verbatim}13711372\item Now for the key exchange. At this point everybody1373should know $E$, $P$, $aP$ and $bP$. Only Alice knows1374$a$ and only Bob knows $b$. Alice computes $a(bP)$ and1375Bob computes $b(aP)$. The Adversary, not knowing $a$1376or $b$, sits there frustrated. Meanwhile Alice and Bob1377have agreed on a shared secret.1378\begin{verbatim}1379sage: b*(a*P)1380(260 : 99 : 1)13811382sage: a*(b*P)1383(260 : 99 : 1)1384\end{verbatim}13851386\item Nonetheless, since the numbers are so small, the1387adversary {\em can} figure out $a$. E.g.,1388\begin{verbatim}1389Q = P1390aP = E([54, 426])1391for n in range(1,1000):1392if Q == aP:1393print n1394break1395else:1396Q = Q + P1397\end{verbatim}1398NOTE: There are better methods than the above simplistic1399brute force approach. But even the better methods aren't1400very good.14011402\item Go through each of the above steps, but with a much1403larger prime $p$, e.g., with 40 digits (basically just1404change all the $1000$'s above to $10^{40}$'s). Note that1405it isn't noticeably slower. The only difference is1406that the Adversary's job is {\em \bf \red \large much harder}.1407\end{enumerate}14081409Once you have a shared secret, you can use it to encrypt a message in1410various ways, many very complicated. A very simple way is to simply1411add (modulo $10$ each digit of the shared secret key to the digits of1412your ``message'' (which we encode as a number).14131414\subsection{A serious cryptosystem that was deployed: MS-DRM}1415There is another famous elliptic curve cryptosystem1416that involves elliptic curves. Read about it in detail1417in Section 6.4.2 of my book, which is at \\1418{\tt http://modular.math.washington.edu/ent}.14191420%\subsection{Encoding a message as a list of points on a curve}1421%It is also possible to actually encode messages as points on1422142314241425\end{document}142614271428