CoCalc Public Fileswww / simuw06 / notes / notes.tex
Author: William A. Stein
1\documentclass{article}
2\include{macros}
3\newcommand{\url}[1]{\begin{center}{\tt #1}\end{center}}
4\newcommand{\code}[1]{{\blue\tt #1}}
5\usepackage{graphicx}
6\usepackage{color}
7\usepackage{pstricks}
8\title{The Congruent Number Problem:\\A Thousand Year Old Unsolved Problem}
9\author{William Stein ({\tt http://modular.math.washington.edu})}
10\date{SIMUW 2006}
11
12\newcommand{\computation}{{\blue\sc\underline{Computation}:} }
13\newcommand{\theory}  {{\blue\sc\underline{Theory}:} }
14\newcommand{\research}{{\blue\sc\underline{Research}:} }
15\renewcommand{\sage}{{\blue\SAGE\xspace}}
16
17\begin{document}
18\maketitle
19
20\begin{abstract}
21  One of the oldest unsolved problems in mathematics is to determine
22  the {\em congruent numbers}: {\em Give a way to decide whether or
23    not an integer is the area of a right triangle with rational side
24    lengths.}  For example, 6 is the area of the right triangle with
25  side lengths 3, 4, and 5.  But 1 is not a congruent number. What
26  about 2006? This workshop will take us from ancient algebra to a
27  major modern conjecture in number theory that has a million dollar
28  bounty: the Birch and Swinnerton-Dyer Conjecture.
29\end{abstract}\vspace{-7ex}
30
31\begin{center}
32\includegraphics[width=0.7\textwidth]{graphics/tri}\vspace{-7ex}
33\end{center}
34The first few congruent numbers:
35{\tiny\noindent{}5, 6, 7, 13, 14, 15, 20, 21, 22, 23, 24, 28, 29, 30, 31, 34,
36  37, 38, 39, 41, 45, 46, 47, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65,
37  69, 70, 71, 77, 78, 79, 80, 84, 85, 86, 87, 88, 92, 93, 94, 95, 96,
38  101, 102, 103, 109, 110, 111, 112, 116, 117, 118, 119, 120, 124,
39  125, 126, 127, 133, 134, 135, 136, 137, 138, 141, 142, 143, 145,
40  148, 149, 150, 151, 152, 154, 156, 157, 158, 159, 161, 164, 165,
41  166, 167, 173, 174, 175, 180, 181, 182, 183, 184, 188, 189, 190,
42  191, 194, 197, 198, 199, 205, 206, 207, 208, 210, 212, 213, 214,
43  215, 216, 219, 220, 221, 222, 223, 224, 226, 229, 230, 231, 237,
44  238, 239, 240, 244, 245, 246, 247, 248, 252, 253, 254, 255, 257,
45  260, 261, 262, 263, 265, 269, 270, 271, 276, 277, 278, 279, 280,
46  284, 285, 286, 287, 291, 293, 294, 295, 299, 301, 302, 303, 306,
47  308, 309, 310, 311, 312, 313, 316, 317, 318, 319, 320, 323, 325,
48  326, 327, 330, 333, 334, 335, 336, 340, 341, 342, 343, 344, 348,
49  349, 350, 351, 352, 353, 357, 358, 359, 365, 366, 367, 368, 369,
50  371, 372, 373, 374, 375, 376, 380, 381, 382, 383, 384, 386, 389,
51  390, 391, 395, 397, 398, 399, 404, 405, 406, 407, 408, 410, 412,
52  413, 414, 415, 421, 422, 423, 426, 429, 430, 431, 434, 436, 437,
53  438, 439, 440, 442, 444, 445, 446, 447, 448, 453, 454, 455, 457,
54  461, 462, 463, 464, 465, 468, 469, 470, 471, 472, 476, 477, 478,
55  479, 480, 485, 486, 487, 493, 494, 495, 496, \ldots,
561974, 1975, 1976, 1980, 1981, 1982, 1983, 1984, 1989, 1990, 1991, 1995, 1997, 1998,
571999, 2000, 2004, 2005, 2006, 2007, 2008, 2009,\ldots }
58
59\tableofcontents
60
61\newpage
62\noindent{\bf Goals:}
63\begin{itemize}
64\item Learn about a major open problem  in number
65  theory.
66\item Learn to use \sage{} to draw plots and do
67  computations.
68\item Learn about elliptic curves: groups, public-key
69cryptography, the BSD conjecture.
70\end{itemize}
71
72
73\section{Rational Right Triangles}
74\begin{enumerate}
75\item      Statement of the congruent number problem.
76\item      Explain what enumerate means''.
77\item      Explain how to enumerate all right triangles with integer side
78      lengths -- Pythagorean triples: draw graph of circle; draw line;
79      find other point of intersection; write it as $(x,y)$ with
80      $x,y$ in terms of $t$.
81\item SAGE tutorial:
82\begin{enumerate}
83\item What is SAGE?
84\item SAGE website.
85\item SAGE notebook: everyone create a worksheet.
86\end{enumerate}
87\end{enumerate}
88\begin{itemize}
89      \item \computation
90\begin{itemize}
91\item Computer lab orientation.
92\item Introduction to \sage.
93\item Write a program to enumerate rational numbers (make table).
94\item Write a program to enumerate Pythagorean triples (make table).
95\item Write a program that enumerates rational right
96triangles (make table).
97\item Write a program that enumerates congruent numbers (make table).
98\item Draw plots of numerous rational right triangles (use the {\tt polygon}
99command in \sage).
100\end{itemize}
101      \item \theory{}
102\begin{itemize}
103\item Give a way to enumerate all rational numbers.
104\item Give a way to enumerate all rational right triangles.
105   \item Prove that $n$ is a congruent number if and only if $nk^2$ is
106a congruent number for any positive integer $k$.
107\item Give a way to enumerate all congruent numbers.
108I.e., a procedure that outputs only congruent numbers and
109  will eventually output any given congruent number.
110\item Give an explicit parametrization of all rational solutions
111  $(x,y)$ to the equation $5x^2 - y^2 = 4$.
112\item Give an example of an equation $ax^2 + by^2=1$ with
113$a,b\in\Q$ and $a,b>0$ that has no rational solutions $(x,y)$.
114\end{itemize}
115
116\item \research{}
117\begin{itemize}
118\item Generalize the enumeration method from above to
119a method to find all rational solutions to any equation
120$ax^2+by^2 = c$, when you're given one solution $P=(x,y)$.
121\item Use the internet to try to figure out what the local-to-global
122  principle for binary quadratic forms'' is.  Give examples that
123  illustrate it.
124\item {\bf\red Open problem:} Consider an equation $y^2 = f(x)$ with $f$ a
125  polynomial of degree $5$.
126  It is a very deep theorem (of Fields Medalist Gerd Faltings) that
127  there are only finitely many rational solutions $(x,y)\in\Q^2$
128  of $y^2 = f(x)$.  It is an open problem to give an algorithm that
129  takes as input $f$ and outputs all the solutions to $y^2=f(x)$.  This
130  is currently a very active area of research.
131
132\end{itemize}
133
134\end{itemize}
135
136\section{Congruent Numbers and Elliptic Curves}
137Today's workshop is about the connection between congruent
138numbers and elliptic curves.
139\begin{enumerate}
140\item Daily crashing of the SAGE Notebook.
142using mathematica/maple/etc from it.
143\item Why are they called congruent numbers''? Connection between
144congruent numbers and congruences'' modulo $n$.
145\item 10-minute break.
146\item Definition of elliptic curve.
147\item Connection between congruent numbers and elliptic curves.
148\end{enumerate}
149
150\begin{itemize}
151      \item \computation
152       \begin{itemize}
153       \item Find the point on an elliptic curve corresponding
154         to the $(3,4,5)$-triangle.
155       \item Find the point on an elliptic curve corresponding
156         to a rational right triangle with area $2006$.
158         numbers up to $1000$, and look for patterns, e.g., reduce the
159         congruent numbers modulo $8$, etc., and see if you notice
160         anything.
161       \item Find a rational number $x$ such that $x-6, x, x+6$ are all perfect squares.
162       \item Find a rational number $x$ such that $x-2006, x, x+2006$ are all perfect squares.
163       \item Let $n$ be the year you were born.  Is it possible to
164find a rational number $x$ such that $x-n, x, x+n$ are all perfect
165squares?
166%Write a function (using a computer) that takes as input a
167%         congruent number $n$ and outputs three rational numbers
168%         $a,b,c$ such that $a,b,c$ are all squares of rational
169%         numbers, and $b = a+n$, $c = b+n$, i.e., $a,b,c$ are
170%         congruent modulo~$n$''.
171       \end{itemize}
172      \item \theory{}
173\begin{itemize}
174\item Prove that if $n$ is a congruent number then there exists a
175  rational number $x$ such that
176  $x-n$, $x$, and $x+n$ are all perfect squares of rational numbers.
177
178{\small [[Hint: Let $X<Y<Z$ be sides of a rational right
179triangle with area $n$.  Let $x = (Z/2)^2$.]]}
180\item Suppose $n$ is an integer and there exists a rational
181number $x$ such that $n-x$, $n$, and $n+x$ are all perfect squares.
182Prove that $n$ is a congruent number.
183{\small [[Hint: from Koblitz's book (see page 4 of scan on website).
184Let $X = \sqrt{x+n} - \sqrt{x-n}$,
185$Y = \sqrt{x+n} + \sqrt{x-n}$,
186$Z = 2\sqrt{x}$. Then $X,Y,Z$ are the sides of a right
187triangle and are all rational, and the triangle has
188area $n$.]]}
189
190\item Think about problems with a similar feel:
191\begin{enumerate}
192\item Which integers are the
193  area of a square with rational side lengths?
194\item Which integers are the
195perimeter of a square with rational side lengths?
196\item Which integers are the
197  area of a rectangle with rational side lengths?
198\end{enumerate}
199           \item
200Let~$n$ be a rational number.   Prove that there is a bijection between
201$$202 A = \left\{(a,b,c) \in \Q^3 \,:\, \frac{ab}{2} = n,\, a^2 + b^2 = c^2\right\} 203$$
204and
205$$206 B = \left\{(x,y) \in \Q^2 \,:\, y^2 = x^3 - n^2 x, \,\,\text{\rm with } y \neq 0\right\} 207$$
208given explicitly by the maps
209$$210 f(a,b,c) = \left(-\frac{nb}{a+c},\,\, \frac{2n^2}{a+c}\right) 211$$
212and
213$$214 g(x,y) = \left(\frac{n^2-x^2}{y},\,\, 215 -\frac{2xn}{y},\,\, \frac{n^2+x^2}{y}\right). 216$$
217
218%\item Find a linear change of variables that gives
219%a one-to-one correspondence between points on
220%$ny^2 = x^3 + ax^2 + 221 222\end{itemize} 223 \item \research{} 224\begin{itemize} 225\item Try to say something about which integers are the perimeter of a 226 right triangle with rational side lengths. Try to convert this 227 question to a question about solutions to equations. 228\item Be creative and come up with similar problems, e.g., which 229 integers are the area of an equilateral triangle with rational side 230 lengths, etc., some very hard, and convert each to a diophantine 231 equation. 232\item Go to 233\begin{verbatim} 234http://www.msri.org/publications/ln/msri/2000/introant/ 235yui/1/index.html 236\end{verbatim} 237and read about another difficult generalization 238of the congruent number problem (this was a talk at a serious 239professional research conference, so don't be annoyed if 240you don't understand much of it). 241\end{itemize} 242\end{itemize} 243 244\begin{center} 245%\includegraphics[width=1.1\textwidth, height=0.5\textheight]{graphics/elliptic_curves.png} 246\mbox{\hspace{-8.5em}\includegraphics[bb=0 0 500 500]{graphics/elliptic_curves.png}} 247\end{center} 248For fun -- the above are a bunch of elliptic curves, along 249with their {\bf Cremona labels''}. 250 251\newpage 252 253\section{Congruent Numbers and Elliptic Curves: II} 254\begin{enumerate} 255\item {\bf\blue The Bijection Revisited Conceptually:} (75 minutes) 256\begin{enumerate} 257 \item (2 minute) Definition of {\em congruent number}. 258 \item (2 minute) Definition of {\em elliptic curve}. 259 \item (40 minutes) {\em Bijection} between points and congruent triangles: revisited. 260In particular, here is a {\red conceptual way} to think about it. 261The set of rational right triangles with area$n$is 262the same as the set of simultaneous solutions to the 263system of equations 264$$265 a^2 + b^2 = c^2, \qquad \frac{ab}{2} = n. 266$$ 267This is the intersection of two quadratic surfaces in$3$-space, 268hence a curve. That curve turns out, after an appropriate 269change of variables, to be the elliptic curve$y^2 = x^3 - n^2 x$. 270Exercise: ...6 steps... (Solution presentation: 30 minute). 271\end{enumerate} 272 273\item {\bf\blue Break:} (10 minute). 274 275\item {\bf\blue Perimeter:} (15 minute) Discuss the problem of which integers are the 276perimeter of a right triangle with rational side lengths. 277Again, the set of such triangles for a given$m$is the 278set of simultaneous solutions to 2 equations: 279$$280 a^2 + b^2 = c^2, \qquad a+b+c = m. 281$$ 282This is the intersection of a quadratic surface and a plane, 283hence a quadratic curve. 284(Exercise -- 15 minutes trying 285this further; presentation of solution.) 286 287%\item {\bf\blue Graphing Elliptic Curves} (20 minutes): 288%Show how to use SAGE to define and graph elliptic curves. 289%(Exercise -- experiment for 20 minutes doing this; presentations.) 290 291\item {\bf\blue Generating New Points on Elliptic Curves from Other Points} 292(30 minutes): 293Explain how it works. Show how to use SAGE to do it. 294(Exercise -- 30 minutes doing this (and getting new triangles); presentations.) 295\end{enumerate} 296 297\begin{itemize} 298 \item \computation 299 300 \begin{itemize} 301 \item Find a triangle with perimeter$6$. Hint: rescale 302 the$3,4,5$triangle. How does rescaling change the perimeter? 303 304 \item Find four distinct right triangles with area$6$. 305 306% \item Draw graphs using SAGE of the set of real solutions to several 307% elliptic curve equations, e.g.,$y^2=x^3+1$,$y^2=x^3-3x+1$, and 308%$y^2=x^3-x$. 309%\begin{verbatim} 310%sage: E = EllipticCurve([-3, 1]) 311%sage: print E 312%Elliptic Curve defined by y^2 = x^3 - 3*x +1 over Rational Field 313%sage: show(plot(E)) 314%\end{verbatim} 315 316 \item Let$E$be the elliptic curve defined by 317$y^2 = x^3 - 36x$, 318 and let$P=$319Compute$P, 2P, 3P, 4P$320by enter$E$and$P$into \sage{} and compute the given sums. 321Trying computing lots of other points too. 322\begin{verbatim} 323sage: E = EllipticCurve([-36,0]) 324sage: P = E([...]) 325sage: 2*P 326\end{verbatim} 327\end{itemize} 328 329\item \theory{} 330 \begin{itemize} 331\item Fix an integer$n$. Show that the rational right triangles 332with area$n$are in bijection 333with the solutions to$y^2=x^3-n^2x$with$y\neq 0$as follows: 334\begin{enumerate} 335\item Think purely conceptually (don't write anything down!): 336\begin{enumerate} 337\item Imagine the surface 338$$339 a^2 + b^2 = c^2 340$$ in three-dimensional space. 341\item Next imagine the surface 342$$343 \frac{ab}{2} = n 344$$ in three-dimensional space. 345\item Finally, imagine the intersection of those two surfaces. 346You should be visualizing a curve in three dimensional space. 347\end{enumerate} 348 349\item Solve for$a$in the equation$ab/2 = n$and substitute 350it into$a^2 + b^2 = c^2$to obtain an equation of the curve 351you visualized in three space in the previous problem. 352You should be able to put this curve in the form 353$$354 4n^2 + X^4 = Y^2. 355$$ 356(You'll have to let$X$and$Y$equal something involving 357$a$and$b$.) 358\item Replace$X$by$y_1$and$Y$by$x_1+y_1^2$in the 359equation for your curve. Simplify and get another curve 360(but in the variables$x_1$and$y_1$): 361$$3624n^2 = x_1^2 + 2 y_1^2 x_1 363$$ 364You should be able to do all this by hand. But if you want 365to use a computer, here's an example of how in SAGE: 366\begin{verbatim} 367sage: X = gp('X'); Y = gp('Y'); x_1 = gp('x_1') 368sage: y_1 = gp('y_1'); n = gp('n') 369sage: print (Y^2).subst(Y,x_1+y_1^2).subst(X, y_1) 370sage: print (4*n^2 + X^4).subst(Y,x_1+y_1^2).subst(X, y_1) 371x_1^2 + 2*y_1^2*x_1 + y_1^4 372y_1^4 + 4*n^2 373\end{verbatim} 374(In SAGE the command {\tt gp('stuff')} makes a formal variable, 375and {\tt subst} allows you to do formal substitutions.) 376\item Multiply both sides of the equation you obtain by$x_1$, 377then replace$x_1$by$x_2$and$y_1$by$y_2/x_2$, to obtain: 378$$379 4n^2 x_2 = x_2^3 + 2y_2^2. 380$$ 381 382\item Do a few additional manipulations to finally obtain 383the equation 384 $$385 y^2 = x^3 - n^2x. 386$$ 387\item If you combine everything you've done so far you get a bijection 388 from yesterday (you do not have to show this). Moreover, you can 389 now go back and forth between solutions to$ y^2 = x^3 - n^2x $and 390 rational right triangles with area$n$. For example, try this with 391$n=6$. 392\begin{enumerate} 393\item Show that the point on the cubic$y^2 = x^3 - 36x$394that corresponds to the$3,4,5$395triangle is$(-3,9)$. 396\item Use \sage{} to find another point$Q$on$y^2 = x^3 - 36x$. 397\item Find the triangle corresponding to$Q$. Verify that it 398really does have area$6$. 399 400\end{enumerate} 401\end{enumerate} 402 403 \end{itemize} 404 405\item \research{} 406 \begin{itemize} 407 \item Say something about 408 perimeters of rational right triangles. Convert this question to 409 a question about solutions to some equation (as bove). Solve this other 410 equation. Give a systematic way to enumerate all rational right 411 triangles with given perimeter. 412 \end{itemize} 413 414% \begin{itemize} 415% \item Let$F(x,y)$be a polynomial in two variables. 416% We call each of the summands$x^i y^j$appearing in$F$417% a {\em monomial}, and say it has degree$i+j$. The {\em degree} of 418%$F$is the largest degree of any monomial appear in$F$. 419 % The {\em homogenization}$G$of$F$is the polynomial in$x,y,z$420% got by multiplying each monomial appearing in$F$by the power of$z$421% so that the degree of every monomial in$G$is the same as the degree 422% of$F$, e.g., the homogenization of$F = x^3 - 3 y^2 + 17x$is 423%$G = x^3 -3 y^2z + 17 xz^2$. 424 425% \begin{enumerate} 426% \item What is the degree of$x^3 + y^3 +1$? What is the 427% degree of$x^3y^2 + xy - y^5$? What is the degree of$x^2y^2 + x^3 + 1$? 428% \item What is the homogenization of$y^2 = x^3 - x$? 429% What is the homogenization of$x^2y^2 + x^3 + 1$? 430% What is the homogenization of$y^2 + y = x^3 + x^2 - 2x$? 431% What is the homogenization of$y^2 = x^3 $? 432%\end{enumerate} 433% \end{itemize} 434% \item \research{} 435% \begin{itemize} 436% \item "Rank" of elliptic curves (average, maximal) 437% \item What about the points with$x=0$? 438% \item What about when cubic has a double root 439% (multiplicative or additive group). 440% \end{itemize} 441\end{itemize} 442 443 444 445 446 447\newpage 448\section{Elliptic Curve Groups} 449\begin{enumerate} 450\item (15 minutes) Presentation -- Perimeters of right triangles? 451 Patterns in congruent numbers modulo~$8$? 452\item (30 minutes) Definition of a {\blue \em group}. 453\begin{definition} 454An {\red \bf abelian group} 455is a set$X$equipped with a binary operation$+$456and an element$0\in X$such that for all$a,b,c \in X$, 457\begin{enumerate} 458\item (closure)$a+b \in X$, 459\item (identity)$0 + a = a + 0 = a$, 460\item (associativity)$a + (b + c) = (a + b) + c$, 461\item (inverses) for every$a$in$X$there is$d$such that$a+d = 0$, 462\item (commutativity)$a + b = b + a$. 463\end{enumerate} 464\end{definition} 465 466{\bf Examples:} 467\begin{enumerate} 468\item The {\red\bf integers}$\Z = \{0,-1,1,-2,2,-3,3,\ldots\}$under addition. 469\item The {\red\bf rational numbers}$\Q$under addition. 470\item The {\red\bf integers}$\{0,1,\ldots, n-1\}$under {\red\bf addition 471 modulo$n$}. 472\item Let$p$be a prime. The {\red\bf integers}$\{1,\ldots, p-1\}$473under {\red\bf multiplication modulo$p$}. 474This is called {\red$\F_p^*$}. 475\end{enumerate} 476 477 478\item (15 minutes) Experiment with some abelian groups in \sage. 479 480\item (10 minutes) Break. 481 482\newpage 483\item (20 minutes) Definition of elliptic curve groups. 484 485\begin{definition} 486Fix integers$a$and$b$. 487Let {\red$E(\Q)$} be the set of solutions to$y^2 = x^3 + a x + b$488along with one extra point'' which we call$\cO$which is 489the additive$0$element. This is an 490abelian group (note: the associative law takes a {\em lot} of work to prove!). 491\end{definition} 492 493 494\item (30 minutes) Participants: Graph elliptic curves. 495Then {\bf\blue derive an algebraic formula} (by hand) for the 496group operation. 497 498\item (15 minutes) Elliptic curves modulo$p$. 499Fix integers$a$and$b$and a prime$p$. 500Let {\red$E(\F_p)$} be the set of solutions to$y^2 \con x^3  + a x + b\pmod{p}$501with$0\leq x < p$and$0\leq y < p$along with a formal extra 502point$\cO$. This group is central in both cryptography (in making 503{\em and} cracking cryptosystems) and the Birch and Swinnerton-Dyer 504conjecture! I will explain how in both cases next week. 505 506\item (15 minutes) Participants: 507Graph and compute with some elliptic curves modulo$p$. 508 509\end{enumerate} 510 511\newpage 512\subsection{Elliptic Curves over$\Q$} 513\begin{itemize} 514 \item \computation 515\begin{itemize} 516\item Play around with each of the above groups in \sage. 517Here are examples of how to compute with each of the 518groups listed above in \sage{} to get you started. 519Be creative and experiment! 520\begin{verbatim} 521sage: ZZ 522Integer Ring 523sage: a = ZZ(5); b = ZZ(7); a+b 52412 525 526sage: QQ 527Rational Field 528sage: QQ(3/4) + QQ(2/3) 52917/12 530 531sage: R = IntegerModRing(12) 532sage: print R 533Ring of integers modulo 12 534sage: R(7) + R(8) 5353 536 537sage: R = FiniteField(7) 538sage: print R 539Finite Field of size 7 540sage: R(4)*R(5) 5416 542\end{verbatim} 543 544\item Compute with elliptic curves over$\Q$. Here 545is an example to get you started. 546\begin{verbatim} 547sage: E = EllipticCurve([-36,0]) 548sage: E 549Elliptic Curve defined by y^2 = x^3 - 36*x over Rational Field 550sage: P = E([-3,9]) # or use E.gens(proof=False) 551sage: P + P 552(25/4 : -35/8 : 1) 553\end{verbatim} 554 555 556\item Draw some graphs of elliptic curves (using the new program 557I just wrote!). Here 558is an example to get you started: 559\begin{verbatim} 560sage: E = EllipticCurve([-36,0]) 561sage: P = plot(E,rgbcolor=(0,0,1)) 562sage: pnt = E([-3,9]) 563sage: pnt2 = 2*pnt 564sage: c1 = point(pnt, pointsize=100) 565sage: c2 = point(pnt2, rgbcolor=(1,0,0), pointsize=100) 566sage: show(P + c1 + c2) 567\end{verbatim} 568%\item 569%Write a program that outputs 20 rational right triangles 570%with area$6$. Plot some of these. 571\end{itemize} 572 \item \theory{} 573\begin{itemize} 574%\item The group has a point$(x,y)$with$y\neq 0$if and only if$n$is 575%a congruent number. 576%\item Geometric proof that composition law is associative 577%[for people who love geometry -- [[copy the argument from Silverman-Tate 578%here]]] 579\item 580Let$E$be an elliptic curve 581given by an equation$y^2=x^3+ax+b$. 582Prove that the following steps can be used to compute 583$+$on$E$: Given$P_1, P_2$, 584this algorithm computes the third point$R=P_1+P_2$. 585\begin{enumerate} 586\item{}[Is$P_i=\O$?] If$P_1=\O$set$R=P_2$or if$P_2=\O$set$R=P_1$587and terminate. Otherwise write$(x_i,y_i)=P_i$. 588\item{}[Negatives] If$x_1 = x_2$and$y_1 = -y_2$, set$R=\O$and terminate. 589\item{}[Compute$\lambda$]\label{alg:grouplaw_3} 590Set$\ds \lambda = \begin{cases}
591 (3x_1^2+a)/(2y_1) & \text{if }P_1 = P_2,\\
592(y_1-y_2)/(x_1-x_2) & \text{otherwise.}
593\end{cases}$\\ 594\item{}[Compute Sum]\label{alg:grouplaw_4} Then 595$R = \ds \left(\lambda^2 -x_1 - x_2, -\lambda x_3 - \nu\right)$, 596where$\nu = y_1 - \lambda x_1$and$x_3=\lambda^2 -x_1 - x_2$597is the$x$-coordinate of$R$. 598\end{enumerate} 599\end{itemize} 600 \item \research{} 601\begin{itemize} 602\item Using the Internet find two web pages that define abelian 603groups. Understand the definitions (perhaps by copying them down 604onto a piece of paper). Do they agree with the definition 605that I gave above? 606%\item It is true that if$n$is a congruent number, there are infinitely 607% many distinct rational right triangles with area$n$. 608\end{itemize} 609 610\end{itemize} 611 612 613\subsection{Elliptic Curves Modulo$p$} 614 Definition, arithmetic, point enumeration, 615 elliptic curve cryptography (discrete log problem; diffie-hellman). 616 617\begin{itemize} 618 \item \computation 619\begin{itemize} 620\item Compute with elliptic curves modulo a prime$p$. Here 621is an example to get you started. 622\begin{verbatim} 623sage: E = EllipticCurve(FiniteField(43), [-36,0]) 624sage: E 625Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 43 626sage: P = E([-3,9]) 627sage: P + P 628(17 : 1 : 1) 629\end{verbatim} 630\item Graph some elliptic curves modulo$p$: 631\begin{verbatim} 632sage: E = EllipticCurve(FiniteField(13), [-36,0]) 633sage: P = plot(E,rgbcolor=(0,0,1),pointsize=100) 634sage: P.show(dpi=200) 635\end{verbatim} 636\end{itemize} 637 638% \begin{itemize} \item draw graphs of the groups (set of all points) 639% \item compute group law explicitly (and graph the cycle get 640% by adding one point over and over). 641% \item number of points over$\F_p$for lots of$p$(the Sato-Tate 642% distribution). 643% \item Hasse bound (proof beyond scope, but statement is easy, and numerical 644% evidence is too). 645% \end{itemize} 646 \item \theory{} 647 \begin{itemize} 648 \item Given$P$and a positive integer$n$, it is fairly 649 straightforward to compute$nP = P + P + \cdots + P$. Given 650$P$and$Q$where you know that$Q=nP$for some$n$(even 651 though you don't know$n!$), invent a way to find$n$(it 652 doesn't have to be fast). 653 \end{itemize} 654% \item \research{} 655% \begin{itemize} 656% \item Discrete log problem. 657% \item Diffie-hellman and El Gammal cryptosystem -- see Sandor's talks later. 658% \end{itemize} 659\end{itemize} 660 661 662\newpage 663\section{The Birch and Swinnerton-Dyer Conjecture (Monday)} 664\begin{center} 665\includegraphics[bb=0 0 550 300 height=13em, width=25em]{graphics/swinnerton_dyer-count.png} 666\end{center} 667\begin{enumerate} 668\item (15 minutes) Congruent number problem; connected 669to elliptic curves; we need to understand when elliptic curves 670have points on them. 671\item (15 minutes) Daily crashing of the SAGE Notebook -- some 672 improvements I made over the weekend: computing \code{E.points()} 673 for$E$an elliptic curve modulo~$p$is now very fast; the Notebook 674 interface is generally more robust and much easier to interrupt; 675 \code{foo??} gives source code even for functions you enter or in 676 cong.sage if you do \code{attach cong.sage}; can write, e.g., 677 \code{plot(..., hue=...)} instead of \code{plot(..., 678 rgbcolor=hue(...))}. So please, right now, {\red try hard to 679 crash'' your personal SAGE Notebook}, i.e., get it in an 680 unresponsive state. Don't worry, I can easily restart all of them. 681\item {\blue\bf The Conjecture}. 682The Birch and Swinnerton-Dyer conjecture was made in the 1960s 683based on numerical computations carried out on EDSAC: 684\includegraphics[bb=0 0 300 180]{graphics/edsac.png} 685 686Let$n$be a positive square-free integer. This means 687that no perfect square divides$n$. 688Let$E_n$be the elliptic curve $$E_n: \quad y^2 = x^3 - n^2x.$$ 689If$n$is odd, let$N = 32n^2$, and if$n$690is even, let$N=16n^2$. The number$N$is called 691the {\blue\em conductor of$E_n$}. 692 693For any prime$p\nmid 2n$, 694let 695$$696 a_p = p + 1 - \#E_n(\F_p), 697$$ 698where$\#E_n(\F_p)$is the number of points on the elliptic curve 699$E_n$viewed modulo$p$. 700If$p\mid 2n$, let$a_p = 0$. 701If$m, r$are coprime integers, let$a_{mr} = a_m a_r$. 702If$p\nmid 2n$let$a_{p^r} = a_{p^{r-1}} a_p - p a_{p^{r-2}}$, 703and if$p\mid 2n$let$a_{p^r} = 0$. 704Finally, let 705$$706 L(E_n,1) = \begin{cases} 707 0 & \text{if n\con 5,6,7\pmod{8}}\\ 708 \ds 2 \cdot \sum_{k=1}^{\infty} \frac{a_k}{k} \cdot e^{-2\pi k/\sqrt{N}} & \text{otherwise}. 709\end{cases} 710$$ 711\begin{conjecture}[Birch and Swinnerton-Dyer]\mbox{}\vspace{-4ex}\\ 712\begin{center} 713We have$L(E_n,1) = 0$if and only if$E_n(\Q)$is infinite. 714\end{center} 715\end{conjecture} 716(Stated in a special cases.) 717 718This is a {\em\red major open problem} in number theory. {\em If 719I don't solve this problem, I hope one of you does!} 720 721\begin{proof}[Heuristic Proof''] 722(This is a {\em\red\bf fake} proof''.) 723 If$E_n(\Q)$is infinite then the numbers$\#E_n(\F_p)$will 724tend to be {\em\large big}, since you get lots of elements 725of$E_n(\F_p)$by reducing the elements of$E_n(\Q)$726modulo$p$. Thus$a_p = p+1 - \#E_n(\F_p)$will tend 727to be {\em small}. One can prove that$L(E_n,1)\geq 0$, 728so if the$a_p$are small, that will cause'' the 729sum that defines$L(E_n,1)$to be small, i.e.,$0$. 730Conversely if$L(E_n,1)=0$, then the$E_n(\F_p)$are big, 731and the points have to come from somewhere so$E_n(\Q)$732is big. 733\end{proof} 734 735\begin{theorem}[Kolyvagin et al.] 736If$E_n(\Q)$is infinite then$L(E_n,1)=0$. 737\end{theorem} 738This is one direction in the conjecture, and the 739proof is {\em very very difficult}. Put another way, 740this theorem says that if$L(E_n,1)\neq 0$, then$E_n(\Q)$is finite. 741 742 743As the notation suggests,$L(E_n,1)$is the value 744of a function at$1$. I will not define the general 745function, but here are some plots of$L(E_n,s)$for 746various$n$: 747\par 748 749{\hspace{-6em}\noindent$n=1$\includegraphics[bb=0 0 180 150]{graphics/lser1.png} 750$n=6$\includegraphics[bb=0 0 180 150]{graphics/lser6.png}} 751 752{\hspace{-6em}$n=34$\includegraphics[bb=0 0 180 150]{graphics/lser34.png} 753$n=4199$\includegraphics[bb=0 0 180 150]{graphics/lser4199.png}} 754 755I made them using code like 756\begin{verbatim} 757E = EllipticCurve([-6^2,0]) 758L = E.Lseries_dokchitser() 759P = plot(L,0.5,1.5, plot_points=50, plot_division=50, 760 rgbcolor=(0,0,1), thickness=2) 761\end{verbatim} 762 763 764\item Participants -- do the following for$n=1$and$n=34$: 765\begin{enumerate} 766\item Write down$E_n$. 767\item Find the conductor$N$of$E_n$. 768\item Compute (by hand/with computer)$a_1, a_2, a_3, a_4$, and$a_5$. 769 Check your answer with \sage (use {\tt E.an(m)} to compute$a_m$). 770 The point here is to spend some time understanding the 771 definition of$a_m$. 772\item Compute the first$5$terms in the sum 773that defines$L(E_n,1)$. 774 775(You should find that for 776$n=34$we have$L(E_{34},1)=0$, whereas for$n=1$we 777have$L(E_{1},1)\neq 0$.) 778\begin{verbatim} 779sage: E = EllipticCurve([-1^2,0]) 780sage: E.Lseries(1) 7810.65551438857302990 782 783sage: E = EllipticCurve([-34^2,0]) 784sage: E.Lseries(1) 785-0.0000000000000000... (the nonzeros at the end are just errors/noise) 786\end{verbatim} 787 788\item The following SAGE program can be used to compute the 789sum that defines$L(E_n,1)$using any number of terms. 790\begin{verbatim} 791def L(n, prec): 792 E = EllipticCurve([-n^2,0]) 793 v = E.anlist(prec) 794 N = E.conductor() 795 sqrtN = sqrt(N) 796 lval = 2*sum(v[n]/n*exp(-2*pi*n/sqrtN) for n in range(1,prec)) 797 return lval 798\end{verbatim} 799Note: This function is in {\tt cong.sage}. Just type 800\code{attach cong.sage} if you haven't already and it 801will magically be available. Then you can enter 802\code{L?} for help and \code{L??} for source code. 803\end{enumerate} 804 805 806 807\item Participants -- Prove using SAGE calculations and the BSD 808conjecture that none of$1,2,3,4$are congruent numbers. 809\item Participants -- Try to find patterns, any at all, 810in the numbers $$p+1-\#E_n(\F_p)$$ 811for the congruent number curves$y^2 = x^3 - n^2x$. 812E.g., fix$n=1$and compute these numbers for 813primes up to some bound: 814\begin{verbatim} 815E = EllipticCurve([-1,0]) 816for p in primes(2,100): 817 print p, E.ap(p) 818\end{verbatim} 819\end{enumerate} 820\begin{itemize} 821 \item \computation 822\begin{itemize} 823\item This \sage code 824draws the plot below. Try different curves, ranges of primes, etc. 825\begin{verbatim} 826n = 6 827def pl(p): 828 return plot(EllipticCurve(GF(p),[-n^2,0]), rgbcolor=hue(0.7)) 829 830P = [pl(p) for p in primes(5,100) if n%p != 0] 831Q = [[P[4*i+j] for j in range(4)] for i in range(len(P)/4)] 832show(graphics_array(Q)) 833# show(graphics_array(Q), axes=False) # if you don't want axes 834\end{verbatim} 835{\hspace{-10.5em}\includegraphics[bb=0 0 450 350]{graphics/points_mod_p.png}} 836 837%\item Verify using \sage that$N_p = p+1$for$p\con 3\pmod{4}$with 838%$p<1000$, where$N_p$is the number of points on$y^2 = x^3 - x$839%over$\F_p$. (Helpful hint to get you going below.) 840%\begin{verbatim} 841%for p in primes(20): 842% print p, E.Np(p) 843%\end{verbatim} 844 845\item Make a table of values$L(E_n,1)$for each integer$n< 50$. 846How does this compare to the table of congruent numbers$n<50$. 847[Here's how to {\em approximately} compute$L(E,1)$in SAGE:] 848 849\item In this problem$n${\em always} denotes a squarefree 850positive integer$n$(i.e., no perfect squares divide$n$). 851\begin{enumerate} 852\item If$n\con 5,6,7\pmod{8}$then does 853 the Birch and Swinnerton-Dyer conjecture imply that 854$n$is a congruent number? 855\item Are there {\em any} integers$n \con 3\pmod{8}$with$n$a 856congruent number? 857\begin{verbatim} 858EllipticCurve([-1,0]).Lseries(1) 859\end{verbatim} 860\end{enumerate} 861\end{itemize} 862 863\item \theory{} 864\begin{itemize} 865%\item Prove that$N_p = p+1$for$p\con 3\pmod{4}$. 866\item What is the relationship between the 867$a_p$for$E_1$and$E_6$? Make a conjecture based 868on numerical evidence. Note: you can compute 869$a_p$using {\tt E.ap(p)}, e.g., 870\begin{verbatim} 871E = EllipticCurve([-1,0]) 872for p in primes(10): 873 print p, E.ap(p) 874\end{verbatim} 875Can you say anything about the relation between the 876$a_p$for$E_1$and for$E_n$for general$n$? 877\end{itemize} 878 879 \item \research{} 880\begin{itemize} 881\item Find Andrew Wiles's paper on the Birch and Swinnerton-Dyer 882 conjecture at the Clay Math Institute web site 883 \url{http://www.claymath.org/millennium/} and read as much of it 884 as you can. One of their pages says: 885\begin{quote} 886Mathematicians have always been fascinated by the problem of describing all solutions in whole numbers$x,y,z$to algebraic equations like 887$$888 x^2 + y^2 = z^2. 889$$ 890 891Euclid gave the complete solution for that equation, but for more 892complicated equations this becomes extremely difficult. Indeed, in 8931970 Yu. V. Matiyasevich showed that Hilbert's tenth problem is 894unsolvable, i.e., there is no general method for determining when such 895equations have a solution in whole numbers. But in special cases one 896can hope to say something. When the solutions are the points of an 897abelian variety, the Birch and Swinnerton-Dyer conjecture asserts that 898the size of the group of rational points is related to the behavior of 899an associated zeta function$L(s)$near the point$s=1$. In 900particular {\em\blue this amazing conjecture asserts that if$L(1)$is equal 901to$0$, then there are an infinite number of rational points 902(solutions), and conversely, if$L(1)$is not equal to 0, then 903there is only a finite number of such points.}'' 904 905\end{quote} 906 907\item Noam Elkies web page 908\url{http://www.math.harvard.edu/\~{ }elkies/compnt.html} 909has the most extensive data I've seen about congruent numbers. 910Check it out! 911 912\item EDSAC -- search for information online about the 913EDSAC computer. 914\end{itemize} 915\end{itemize} 916 917\newpage 918\section{Square Triangles and Fermat's Last Theorem (Wed morning)} 919 920The numbers$1$,$2$,$3$, and$4$are not congruent numbers. In 921particular,$1$is not. I.e., there is not rational right triangle 922whose area is a perfect square, i.e., there are no square 923triangles''. 924 925\begin{enumerate} 926\item (60 minutes) Watch the Fermat's Last Theorem movie. 927\item (10 minutes) Move to computer lab / break. 928\item (10 minutes) Recall that we know''$1$is not a congruent 929 number from Monday, since$L(E_1, 1) = 0.65551\ldots \neq 0$. But that 930 uses a deep theorem (the proof by Kolyvagin of one direction 931of the Birch and Swinnerton-Dyer conjecture). 932\item (70 minutes) Prove Fermat's Last Theorem for$n=4$, and use this 933 to deduce that$1$is not a congruent number. 934\end{enumerate} 935 936 \begin{itemize} 937 \item \computation 938\begin{itemize} 939\item Via a direct computer search, show there are no right triangles 940 with area$1$and rational side lengths$(a,b,c)$(with$c$the 941 hypotenuse) with the number of digits of the numerators and 942 denominators of$a$,$b$,$c$all$<100$in absolute value. 943\item Look for solutions to$y^2=x^3-x$with both$x,y$rational and 944$y\neq 0$. Fail to find any. 945\end{itemize} 946\item \theory{} You {\em\red definitely} want to work together on these 947 problems, even possibly dividing up into groups and assigning parts 948 to different groups, and also having people search online for help 949 (which is allowed). Make solving all these nicely a community 950 effort. [Credit: This sequence of problems was originally written 951 by the Baur Bektemirov (the first ever winner 952 of the International Math Olympiad gold medal from Kazakhstan), 953 while he was a freshman at Harvard working with me.] 954\begin{enumerate} 955\item\label{ex:pythag} Suppose$a$,$b$,$c$are relatively prime 956 integers with$a^2+b^2=c^2$. Then there exist integers$x$and$y$957 with$x>y$such that$c=x^2+y^2$and either$a=x^2-y^2$,$b=2xy$or 958$a=2xy$,$b=x^2-y^2$. Hint: Recall what we did on day 1 959 where we parametrized Pythagorean triples$a,b,c$: 960\begin{center} 961\mbox{\hspace{-8em}\includegraphics[bb=0 0 400 250 width=0.8\textwidth]{graphics/pythag.png}} 962\end{center} 963 964 965\item\label{ex:flt4} Fermat's Last Theorem for exponent$4$asserts 966 that any solution to the equation$x^4+y^4=z^4$with$x,y,z\in\Z$967 satisfies$xyz=0$. Prove Fermat's Last 968 Theorem for exponent$4$, as follows. 969\begin{enumerate} 970\item Show that if the equation$x^2+y^4=z^4$has no integer 971solutions with$xyz\neq 0$, then Fermat's Last Theorem for exponent~$4$972is true. (Note -- the power of$x$is$2$.) 973\item Prove that$x^2+y^4=z^4$has no integer solutions with$xyz\neq 0$974as follows. 975Suppose$n^2+k^4=m^4$is a solution with$m>0$minimal amongst 976all solutions. Show that there exists a solution with$m$smaller 977using the previous exercise above (consider two cases). 978\end{enumerate} 979 980\item Prove that 1 is not a congruent number by showing that 981the cubic curve$y^2=x^3-x$has no rational solutions 982except$(0,\pm 1)$and$(0,0)$: 983\begin{enumerate} 984\item Write$y=\frac{p}{q}$and$x=\frac{r}{s}$, where$p,q,r,s$are 985all positive integers and$\gcd(p,q)=\gcd(r,s)=1$. Prove that$s\mid
986q$, so$q=sk$for some$k\in\Z$. 987\item Prove that$s=k^2$, and substitute to see that 988$p^2=r^3-rk^4$. 989\item Prove that$r$is a perfect square by supposing 990that there is a prime~$\ell$such that$\ord_{\ell}(r)$is 991odd and analyzing$\ord_{\ell}$of both sides of 992$p^2=r^3-rk^4$. 993\item Write$r=m^2$, and substitute to 994see that$p^2=m^6-m^2k^4$. Prove that$m\mid p$. 995\item Divide through by$m^2$and deduce a contradiction to the 996 previous exercise. 997\end{enumerate} 998 999\end{enumerate} 1000\end{itemize} 1001 1002 1003\newpage 1004\section{An Elementary Criterion (Thursday)} 1005 1006\begin{enumerate} 1007\item ($<1$hour) -- Student presentations: proof of FLT for exponent 4 and 1008no square triangles. 1009\item (10 minutes) -- break 1010\item (30 minutes) -- statement of Tunnell's criterion. 1011Let $$\Theta(q) = 1 + 2\sum_{m\geq 1} q^{m^2} = 10121 + 2q + 2q^{4} + 2q^{9} + \cdots.$$ 1013Let 1014$$f_1 = \Theta(q)\cdot (2\Theta(q^{32}) - \Theta(q^8))\cdot \Theta(q^2)$$ 1015and 1016$$f_2 = \Theta(q) \cdot (2\Theta(q^{32}) - \Theta(q^8))\cdot \Theta(q^4).$$ 1017\begin{theorem}[Waldspurger, Tunnell]\label{thm:tunnell} 1018Suppose$n$is a squarefree integer. If$n$is odd 1019then$L(E_n,1)=0$if and only if the$n$th coefficient 1020of$f_1$is$0$. If$n$is even then$L(E_n,1)=0$1021if and only if the$\frac{n}{2}$th coefficient of$f_2$is$0$. 1022\end{theorem} 1023This is a {\bf\blue very deep theorem}. It allows us to determine 1024whether or not$L(E_n,1)=0$. 1025The Birch and Swinnerton-Dyer conjecture (which is not 1026a theorem) then asserts that$L(E_n,1)=0$if and only if$n$1027is a congruent number. Thus once enough of the 1028Birch and Swinnerton-Dyer conjecture is proved, we'll have 1029an elementary way to decide whether or not a (squarefree) 1030integer$n$is a congruent number. Namely, 1031if$n$is odd then (conjecturally)$n$is a congruent number 1032if and only if 1033$$\#\left\{x,y,z\in\Z \,:\, 2x^2 + y^2 + 32z^2 = n\right\} 1034 = \frac{1}{2} \#\left\{x,y,z\in\Z \,:\, 2x^2 + y^2 + 8z^2 = n\right\}. 1035$$ 1036Simiarly, 1037if$n$is even then (conjecturally)$n$is a congruent number 1038if and only if 1039$$\#\left\{x,y,z\in\Z \,:\, 4x^2 + y^2 + 32z^2 = \frac{n}{2}\right\} 1040 = \frac{1}{2} \#\left\{x,y,z\in\Z \,:\, 4x^2 + y^2 + 8z^2 = n\right\}. 1041$$ 1042 1043 1044\item (30 minutes) -- exercises with Tunnell's criterion. 1045\begin{enumerate} 1046\item Come up with a method to explicitly list 1047each of the above sets. 1048 1049\item Prove that the elementary criterion (involving cardinality of 1050 sets) implies that none of$n=1,2,3,4$are congruent numbers. 1051 1052\item Prove that the elementary criterion (involving cardinality of 1053 sets) implies that$n=5,6,7$are congruent numbers. Then find 1054a right triangle with area$5$. 1055 1056\item Verify with \sage that Theorem~\ref{thm:tunnell} (appears to) 1057hold for$n<20$. Hint: The command 1058\begin{verbatim} 1059f1, f2 = tunnell_forms(30) 1060\end{verbatim} 1061computes the$f_1$and$f_2$defined above, and e.g., \code{f1[3]} 1062returns the coefficient of$q^3$. 1063 1064\item {\bf Question (Nathan Ryan):} Is it possible to decide whether 1065 or not a prime number$p$is a (conjectural) congruent number in 1066 time polynomial in the number of digits of$p$? I.e., if$p$has a 1067 hundred digits is there any hope we could tell whether or not$p$is 1068 (conjecturally) a congruent number i a reasonable amount of time? 1069 [[{\bf\red WARNING: This is an unsolved problem, as far as I 1070 know.}]] 1071\end{enumerate} 1072 1073\end{enumerate} 1074 1075 1076 1077\newpage 1078\section{Square Triangles Revisited} 1079Since there was so much trouble with the proof of Fermat for exponent 1080$4$, let's revisit it. First, Fermat's proof: 1081\begin{quote} 1082if the area of a rational right triangle were a square, then 1083there would also be a smaller one with the same property, and so on, 1084which is impossible.'' 1085\end{quote} 1086OK, that wasn't so helpful. 1087Anyway, we did everything on Thursday except 2b, i.e., 1088suppose that$n^2 + k^4 = m^4$is a solution in positive 1089integers to the equation$x^2 + y^4 = z^4$with$m>0$1090minimal among all possible solutions. Show that there is a 1091a smaller solution, hence deduce a contradiction. 1092\begin{enumerate} 1093\item Case 1: If$n$is even then there exist integers$x,y\geq 0$1094(with$x>y$) such that 1095$$n = 2xy\qquad k^2 = x^2 - y^2 \qquad m^2 = x^2 + y^2.$$ 1096Then 1097 $$1098 (mk)^2 = x^4 - y^4, 1099$$ 1100from which we obtain a smaller solution. 1101 1102\item Case 2: Next assume$n$is odd. The trick is to proceed as 1103 above, but to apply exercise 1 again to the Pythagorean triple$m^2
1104  = x^2 + y^2$and note that various numbers are perfect squares. We 1105 give full details below. 1106 1107There are integers$x,y$with$x>y$such that 1108$$n = x^2 - y^2\qquad k^2 = 2xy \qquad m^2 = x^2 + y^2.$$ 1109 1110Since$2xy=k^2$is a perfect square we can write 1111either$x=u^2$,$y=2v^2$or$x=2u^2$,$y=v^2$for integers 1112$u,v$. 1113 1114\begin{enumerate} 1115\item Case: We have$x=u^2, y=2v^2$, i.e.,$y$is even and 1116$x$is odd (note that$x$must be odd if$y$is even 1117since$n=x^2-y^2$is odd). 1118 Since$m^2 = x^2 + y^2$is itself a Pythagorean 1119triple with$x$odd, we can again apply exercise 1 to find coprime 1120integers$a,b$such that 1121$$1122 x = a^2 - b^2\qquad y = 2ab\qquad z = a^2 + b^2. 1123$$ 1124Then$2v^2 = y = 2ab$, so since$a,b$are coprime we have 1125$a = d^2$,$b=e^2$for integers$d,e$. 1126Since$x=u^2$and$x=a^2-b^2$, we have 1127$$1128 u^2 = d^4 - b^4, 1129$$ 1130which yields a smaller solution to$x^2 + y^4 = z^4$. 1131\item Case: We have$x=2u^2, y=v^2$, i.e.,$y$is odd and 1132$x$is even (note that$y$must be odd if$x$is even 1133since$n=x^2-y^2$is odd). 1134 Since$m^2 = x^2 + y^2$is itself a Pythagorean 1135triple with$y$odd, we can again apply exercise 1 to find coprime 1136integers$a,b$such that 1137$$1138 y = a^2 - b^2\qquad x = 2ab\qquad z = a^2 + b^2. 1139$$ 1140Then$2u^2 = x = 2ab$, so since$a,b$are coprime and 1141have square product we have 1142$a = d^2$,$b=e^2$for integers$d,e$. 1143Since$y=v^2$and$y=a^2-b^2$, we have 1144$$1145 v^2 = d^4 - b^4, 1146$$ 1147which yields a smaller solution to$x^2 + y^4 = z^4$. 1148 1149\end{enumerate} 1150 1151\end{enumerate} 1152 1153 1154\newpage 1155\section{An Elliptic Curve Cryptography (ECC) Tutorial} 1156Elliptic curves are useful far beyond the fact that they shed a huge 1157amount of light on the congruent number problem. For example, many 1158people (probably you!) use them on a daily basis, since they are used 1159to make some of the best public-key cryptosystems (= methods for 1160sending secret data). 1161 1162 1163I think the Wikipedea opening description of Elliptic curve 1164cryptography is OK (no comment about the rest of the article): 1165\begin{quote} 1166 Elliptic curve cryptography (ECC) is an approach to public-key 1167 cryptography based on the algebraic structure of elliptic curves 1168 over finite fields. The use of elliptic curves in cryptography was 1169 suggested independently by Neal Koblitz [1] and Victor S. Miller [2] 1170 in 1985. 1171 1172 Elliptic curves are also used in several integer factorization 1173 algorithms that have applications in cryptography, such as, for 1174 instance, Lenstra elliptic curve factorization, but this use of 1175 elliptic curves is not usually referred to as "elliptic curve 1176 cryptography." 1177 1178 [...] As for other popular public key cryptosystems, no mathematical 1179 proof of difficulty has been published for ECC as of 2006. However, 1180 the U.S. National Security Agency has endorsed ECC technology by 1181 including it in its Suite B set of recommended algorithms. Although 1182 the RSA patent has expired, there are patents in force covering some 1183 aspects of ECC. 1184\end{quote} 1185Note: Neal Koblitz is a math professor here at UW. He wrote the book 1186on the congruent number problem (I scanned some of it for the 1187website). You might see him around this summer, since he's teaching a 1188summer school class. 1189\begin{center} 1190\includegraphics[bb=0 0 75 100]{graphics/koblitz.png} 1191\end{center} 1192 1193{\bf \blue Basic Problem:} {\em How can people or computers send 1194 secret messages to each other without having to send out passwords 1195 ahead of time? How did mathematicians put the guys with briefcases 1196 handcuffed to their hands out of business?} 1197 1198Sandor Kovacs will go into great detail about this question in 1199his course, and you might view today as a preview of some of what 1200he'll do, with the bonus that today you get to try it out on a 1201computer. Today I'll just give you the chance to {\em understand and 1202 play with} one example that addresses this basic problem. 1203 1204\subsection{Elliptic Curves Modulo$p$} 1205Let$p$be a prime number. Consider an equation 1206$y^2 = x^3 + ax + b$with 1207$$a,b \in \F_p = \{0,1,\ldots, p-1\} \qquad\text{(integers modulo p)}$$ 1208such that the cubic$x^3 + ax + b$has distinct roots. 1209The group of points on$E$modulo$p$is 1210$$1211 E(\F_p) = \{(x,y)\in \F_p \times \F_p : y^2 = x^3 +ax + b\} \union \{\cO\}. 1212$$ 1213 1214{\bf Exercise:} Make up several random'' elliptic curves over 1215various random$\F_p$'s in \sage (so {\em not} related to the 1216congruent number problem!). List their points. Plot them. Do a 1217little arithmetic with them. Here is some code to get you 1218started.\vspace{1ex} 1219 1220\noindent{}Finding a random prime$<1000$: 1221\begin{verbatim} 1222sage: next_prime(randrange(1000)) 1223137 1224\end{verbatim} 1225Making up a random curve: 1226\begin{verbatim} 1227sage: p = 137 1228sage: F = FiniteField(p) 1229sage: E = EllipticCurve(F, [F.random_element(), F.random_element()]) 1230sage: print E 1231Elliptic Curve defined by y^2 = x^3 + 45*x + 43 over Finite Field of size 137 1232\end{verbatim} 1233List all points: 1234\begin{verbatim} 1235sage: E.points() 1236[(0 : 1 : 0), (51 : 90 : 1), (57 : 92 : 1), (90 : 34 : 1), ... 1237\end{verbatim} 1238Make a plot: 1239\begin{verbatim} 1240sage: show(plot(E, hue=.9)) 1241\end{verbatim} 1242Do some arithmetic: 1243\begin{verbatim} 1244sage: P = E.points()[1] # first point listed above 1245sage: P 1246(51 : 90 : 1) 1247sage: P + P 1248(57 : 92 : 1) 1249sage: 10*P 1250(131 : 105 : 1) 1251sage: 9393*P 1252(129 : 26 : 1) 1253\end{verbatim} 1254 1255 1256\subsection{Computing$nQ$} 1257Recall from yesterday that computers can compute$a^m \pmod{n}$very 1258quickly, even if$m$is {\bf huge}. They do this by writing$n$1259in binary and doing a few squares and multiplies. Likewise, 1260we can compute$nQ$quickly when$Q$is a point on an elliptic 1261curve modulo$p$. Try it out! 1262\begin{verbatim} 1263sage: p = 137 1264sage: F = FiniteField(p) 1265sage: E = EllipticCurve(F, [F.random_element(), F.random_element()]) 1266sage: P = E.random_element() 1267sage: print P 1268(96 : 94 : 1) 1269 1270sage: time 102000823098320*P 1271(86 : 60 : 1) 1272CPU time: 0.12 s, Wall time: 0.13 s 1273 1274sage: show(plot(P) + plot(102000823098320*P,rgbcolor=(1,0,0))) 1275[[a plot]] 1276\end{verbatim} 1277Now try with an elliptic curve over a huge field. 1278\begin{verbatim} 1279sage: p = next_prime(randrange(10^40)) 1280sage: print p 1281sage: F = FiniteField(p) 1282sage: E = EllipticCurve(F, [F.random_element(), F.random_element()]) 1283sage: P = E.random_element() 1284sage: print P 1285554146695875703931136550843186162763121 1286(493257625218361211096484901389666856690 : 1287 286863248034562484128552069228984577311 : 12881) 1289\end{verbatim} 1290Then multiply... 1291\begin{verbatim} 1292sage: time 909238403284092384209482038402*P 1293(151371634043111300277840422027192273952 : 1294 333732213371771487412281506530764174375 : 12951) 1296CPU time: 0.20 s, Wall time: 0.21 s 1297\end{verbatim} 1298 1299\subsection{Diffie-Hellman -- a way to create a shared secret} 1300The Diffie-Hellman key exchange was the first ever public-key 1301cryptosystem. We will try it out on a elliptic curve here 1302(note: it can also be used directly in$\F_p^* = \{1,\ldots, p-1\}$, 1303as you will learn in Sandor's course). 1304 1305Public key cryptography involves three people'': 1306\begin{itemize} 1307\item Person 1 -- traditionally named Alice 1308\item Person 2 -- traditionally named Bob 1309\item Person 3 -- traditionally called The Adversary 1310\end{itemize} 1311 1312\begin{enumerate} 1313\item Break up into groups of (at least) 3. Choose at least person to 1314 be Alice\footnote{Even a guy could be Alice'', e.g., there is a 1315 guy named Alice Cooper from Phoenix, AZ.}, at least one to be 1316 Bob\footnote{Are there any famous women named Bob?}, and one to be 1317 the Adversary. Each person should have a computer terminal open to 1318 their SIMUW SAGE notebook. Open a common SAGE worksheet that all 1319 three of you can see and use to post messages (by refreshing the 1320 page). I'll explain how to do this. 1321 1322\item In this exercise Alice and Bob will agree on a secret key 1323by sending message {\em in full view} of everybody else. Of course, 1324what they do at there computers gets kept secret -- only the messages 1325are public (in particular, Adversary should not look at the crypto 1326worksheets of Alice and Bob). 1327 1328\item Alice: Choose a random prime$p$and create a random 1329elliptic curve modulo$p$, then choose a random point on this 1330elliptic curve. 1331\begin{verbatim} 1332sage: load cong.sage # defines random_elliptic_curve command 1333sage: E = random_elliptic_curve(next_prime(randrange(1000))) 1334sage: print E 1335Elliptic Curve defined by y^2 = x^3 + 508*x + 42 over Finite Field of size 577 1336\end{verbatim} 1337 1338\begin{verbatim} 1339sage: P = E.random_element() 1340sage: P 1341(386 : 331 : 1) 1342\end{verbatim} 1343Finally, Alice has to tell everybody the random elliptic curve 1344and the random point in such a way that Bob can define it 1345on his computer. In the above example, just report that 1346the prime is$47$, that the curve is \code{EllipticCurve([36,3])}, 1347and the point is$(5,4)$. 1348 1349\item Bob: Choose a random integer$b$(up to about$p$in size) 1350and compute$bP$and tell everyone. 1351\begin{verbatim} 1352sage: b = randrange(1000); b 1353549 1354\end{verbatim} 1355 1356\begin{verbatim} 1357sage: b*P 1358(472 : 340 : 1) 1359\end{verbatim} 1360 1361Announce$(83,362)$to the world. But keep b secret. 1362 1363\item Alice: Do the same thing as Bob, but with your own 1364integer$a$. 1365\begin{verbatim} 1366sage: a = randrange(1000); a 1367779 1368 1369sage: a*P 1370(54 : 426 : 1) 1371\end{verbatim} 1372 1373\item Now for the key exchange. At this point everybody 1374should know$E$,$P$,$aP$and$bP$. Only Alice knows 1375$a$and only Bob knows$b$. Alice computes$a(bP)$and 1376Bob computes$b(aP)$. The Adversary, not knowing$a$1377or$b$, sits there frustrated. Meanwhile Alice and Bob 1378have agreed on a shared secret. 1379\begin{verbatim} 1380sage: b*(a*P) 1381(260 : 99 : 1) 1382 1383sage: a*(b*P) 1384(260 : 99 : 1) 1385\end{verbatim} 1386 1387\item Nonetheless, since the numbers are so small, the 1388adversary {\em can} figure out$a$. E.g., 1389\begin{verbatim} 1390Q = P 1391aP = E([54, 426]) 1392for n in range(1,1000): 1393 if Q == aP: 1394 print n 1395 break 1396 else: 1397 Q = Q + P 1398\end{verbatim} 1399NOTE: There are better methods than the above simplistic 1400brute force approach. But even the better methods aren't 1401very good. 1402 1403\item Go through each of the above steps, but with a much 1404larger prime$p$, e.g., with 40 digits (basically just 1405change all the$1000$'s above to$10^{40}$'s). Note that 1406it isn't noticeably slower. The only difference is 1407that the Adversary's job is {\em \bf \red \large much harder}. 1408\end{enumerate} 1409 1410Once you have a shared secret, you can use it to encrypt a message in 1411various ways, many very complicated. A very simple way is to simply 1412add (modulo$10\$ each digit of the shared secret key to the digits of
1413your message'' (which we encode as a number).
1414
1415\subsection{A serious cryptosystem that was deployed: MS-DRM}
1416There is another famous elliptic curve cryptosystem