Transcript The Ubiquity of Elliptic Curves

The Ubiquity of
Elliptic Curves
Joseph Silverman (Brown University)
Public Lecture – Dublin
Tuesday, 4 September 2007, 7:30 PM
Elliptic Curves
Geometry, Algebra, Analysis
and Beyond…
What is an Elliptic Curve?
• An elliptic curve is an object with a dual nature:
• On the one hand, it is a curve, a geometric object.
• On the other hand, we can “add” points on the curve as
if they were numbers, so it is an algebraic object.
• The addition law on an elliptic curve can be described:
• Geometrically using intersections of curves
• Algebraically using polynomial equations
• Analytically
using functions with complex variables
• Elliptic curves appear in many diverse areas of
mathematics, ranging from number theory to complex
analysis, and from cryptography to mathematical physics.
-3-
The Equation of an Elliptic Curve
An Elliptic Curve is a curve given by an equation
E : y2 = f(x) for a cubic or quartic polynomial f(x)
We also require that the polynomial f(x) has no double
roots. This ensures that the curve is nonsingular.
After a change of variables, the equation takes the
simpler form
E : y2 = x3 + A x + B
Finally, for reasons to be explained shortly, we toss in
an extra point O “at infinity,” so E is really the set
E = { (x,y) : y2 = x3 + A x + B }  { O }
-4-
A Typical Elliptic Curve E
E : Y2 = X3 – 5X + 8
Surprising Fact: We can use geometry to take two
points P and Q on the elliptic curve and define their “sum”
P+Q.
-5-
The Addition Law on an
Elliptic Curve
Adding Points P + Q on E
R
Q
P
P+Q
-7-
Doubling a Point P on E
Tangent Line to E at P
R
P
2*P
-8-
Vertical Lines and an Extra Point at Infinity
O
Add an extra point O “at infinity.”
The point O lies on every vertical line.
P
Q = –P
Vertical lines have no
third intersection point
-9-
Properties of “Addition” on E
Theorem: The addition law on E has the following
properties:
a) P + O = O + P = P
for all P  E.
b) P + (–P) = O
for all P  E.
c) (P + Q) + R = P + (Q + R)
for all P,Q,R  E.
d) P + Q = Q + P
for all P,Q  E.
In mathematical terminology, the addition law + makes
the points of E into a commutative group.
All of the group properties are easy to check except for
the associative law (c). The associative law can be
verified by a lengthy computation using explicit
formulas, or by using more advanced algebraic or
analytic methods.
- 10 -
An Example
E : Y2 = X3 – 5X + 8
The point P = (1,2) is on the curve E.
Using the tangent line construction, we find that
2P = P + P = (– 7/4, – 27/8).
Using the secant line construction, we find that
3P = P + P + P = (553/121, – 11950/1331)
Similarly,
4P = (45313/11664, 8655103/1259712).
As you can see, the coordinates become complicated.
- 11 -
An Addition Formula for E
Suppose that we want to add the points
P1 = (x1,y1) and P2 = (x2,y2)
on the elliptic curve
E : y2 = x3 + Ax + B.
y 2  y1
Let  
if P1  P2
x2  x1
3x12  A
and  
if P1  P2 .
2y1
Then P1  P2  (2  x1  x2,  3  2x1  x2  y1).
Quite a mess!!!!! But…
Crucial Observation: If A and B are rational numbers and
if the coordinates of P1 and P2 are rational numbers,
then the coordinates P1+ P2 and 2P1 are rational numbers.
- 12 -
The Group of Points on E
with Rational Coordinates
The elementary observation on the previous slide
leads to an important result:
Theorem (Poincaré, 1900): Suppose that an elliptic
curve E is given by an equation of the form
y2 = x3 + A x + B
with
A,B rational numbers.
Let E(Q) be the set of points of E with rational
coordinates,
E(Q) = { (x,y)  E : x,y are rational numbers }  { O }.
Then sums of points in E(Q) remain in E(Q).
In mathematical terminology, E(Q) is a subgroup of E.
- 13 -
The Group of Points on E with Other
Sort of Coordinates
In an earlier slide, we drew a picture of E in the
plane. This was the set of points of E with real
coordinates:
E(R) = { (x,y)  E : x,y are real numbers }  { O }.
Similarly, we can look at the points of E whose
coordinates are complex numbers:
E(C) = { (x,y)  E : x,y are complex numbers }  { O }.
And later we’ll look at the set of points E(Fp) whose
coordinates are in a “finite field” Fp.
Key Fact: In any of these sets, we can add points and
stay within the set.
- 14 -
What Does E(R) Look Like?
We saw one example of E(R). It is also possible for E(R) to
have two connected components.
E : Y2 = X3 – 9X
- 15 -
Elliptic Curves and
Complex Numbers
Or…How the Elliptic Curve Acquired
Its Unfortunate Moniker
The Arc Length of an Ellipse
The arc length of a half circle
is given by the familiar integral
x2+y2=a2
-a

a
a
The arc length of a half ellipse
b
-a
a
a2  x 2
is more complicated
x2/a2 + y2/b2 = 1
a
a dx

a
a


a2  1 b2 / a2 x 2
dx
2
2
a x
- 17 -
The Arc Length of an Ellipse
Let k2 = 1 – b2/a2 and change variables x  ax. Then the
arc length of an ellipse is
1
a
1
1 k x
dx
2
1 x
2
2
1 k 2 x 2
1
a
1
(1  x )(1  k x )
1 k 2 x 2
Arc Length  a 
dx
1
y
1
2
2
2
dx
An Elliptic Curve!
with y2 = (1 – x2) (1 – k2x2) = quartic in x.
An elliptic integral is an integral  R ( x, y ) dx , where R(x,y) is
a rational function of the coordinates (x,y) on an “elliptic curve”
E : y2 = f(x) = cubic or quartic in x.
- 18 -
Elliptic Integrals and Elliptic Functions
w
The circular integral

0
dx
1 x 2
is equal to sin-1(w).
Its inverse function w = sin(z) is periodic with period 2.
The elliptic integral
dx
w

has an inverse
x  Ax  B
w = (z) with two independent complex periods 1 and 2.
3
(z + 1) = (z + 2) = (z)
Doubly periodic functions are called
for all z  C.
elliptic functions.
- 19 -
Elliptic Functions and Elliptic Curves
The -function and its derivative satisfy an algebraic
relation
(z)2  (z)3  A(z)  B
This equation looks familiar
The double periodicity of (z) means that it is a function
on the quotient space C/L, where L is the lattice
L = { n11 + n22 : n1,n2  Z }.
1
1+ 2
L
2
(z) and ’(z) are functions on a fundamental parallelogram
- 20 -
The Complex Points on an Elliptic Curve
The -function gives a complex analytic isomorphism
C

L
(z),(z)
E(C)
Parallelogram with opposite
sides identified = a torus
Thus the points of E with coordinates in the complex
numbers C form a torus, that is, the surface of a donut.
E(C) =
- 21 -
Elliptic Curves and
Number Theory
Rational Points on Elliptic Curves
E(Q) : The Group of Rational Points
A fundamental and ancient problem in number theory is
that of solving polynomial equations using integers or
rational numbers.
The description of E(Q) is a landmark in the modern
study of Diophantine equations.
Theorem (Mordell, 1922): Let E be an elliptic curve given
by an equation
E : y2 = x3 + A x + B
with A,B  Q.
There is a finite set of points P1,P2,…,Pr so that every
point P in E(Q) can be obtained as a sum
P = n1P1 + n2P2 + … + nrPr
with n1,…,nr  Z.
In math terms, E(Q) is a finitely generated group.
- 23 -
E(Q) : The Group of Rational Points
A point P has finite order if some multiple of P is O. The
elements of finite order in E(Q) are quite well understood.
Theorem (Mazur, 1977): The group E(Q) contains at
most 16 points of finite order.
The minimal number of points needed to generate the
group E(Q) is much more mysterious!
Conjecture: The number of points needed to generate
E(Q) may be arbitrarily large.
Current World Record: (Elkies 2006) There is an
elliptic curve with
Number of generators for E(Q)  28.
- 24 -
E(Z) : The Set of Integer Points
If P1 and P2 are points on E having integer coordinates,
then P1 + P2 will have rational coordinates, but there is
no reason for it to have integer coordinates.
Indeed, the formulas for P1 + P2 are so complicated, it
seems unlikely that P1 + P2 will have integer coordinates.
Complementing Mordell’s finite generation theorem for
rational points is a famous finiteness result for integer
points.
Theorem (Siegel, 1928): An elliptic curve
E : y2 = x3 + A x + B
with A,B  Z
has only finitely many points P = (x,y) with integer
coordinates x,y  Z.
- 25 -
Elliptic Curves and
Finite Fields
Finite Fields
You may have run across clock arithmetic, where after
counting 0, 1, 2, 3,…,11, you go back to 0.
Another way to view clock arithmetic is that whenever you
add or multiply numbers together, you should divide by 12
and just keep the remainder.
We want to do the same thing, but instead of using 12,
we’ll use a prime number p, for example 3 or 7 or 37.
The Finite Field Fp is the set of numbers
0, 1, 2, …, p–1
with the rule that when we add or multiply two of them, we
are required to divide by p and just keep the remainder.
- 27 -
An Example of a Finite Field
For example, in the finite field F7,
54 2
since 9 divided by 7 leaves remainder 2.
54  6
since 20 divided by 7 leaves remainder 6.
Similarly, in the field F41, we have
11 x 15 = 1 and 23 x 25 = 1 and 19 x 13 = 1 and …
This illustrates why we use a prime p, instead of a number
like 12. In a finite field Fp, every nonzero number has a
reciprocal. So Fp is a lot like the rational numbers Q and the
real numbers R:
In Fp, not only can we can add, subtract, and multiply, we
can also divide by nonzero numbers
- 28 -
Elliptic Curves over a Finite Field
The formulas giving the addition law on E are fine if the
points have coordinates in any field, even if the
geometric pictures don’t make sense.
For example, we can take points with coordinates in Fp.
Example:The curve
E : Y2 = X3 – 5X + 8 modulo 37
contains the points
P = (6,3) and Q = (9,10).
Using the addition formulas, we can compute in E(F37):
2P = (35,11) 3P = (34,25) 4P = (8,6) 5P = (16,19) …
P + Q = (11,10)
3P + 4Q = (31,28) …
- 29 -
E(Fp) : The Group of Points Modulo p
Number theorists also like to solve polynomial equations
modulo p.
This is much easier than finding solutions in Q, since
there are only finitely many solutions in the finite field Fp!
One expects E(Fp) to have approximately p+1 points.
A famous theorem of Hasse (later vastly generalized by
Weil and Deligne) quantifies this expectation.
Theorem (Hasse, 1922): An elliptic curve equation
E : y2  x3 + A x + B (modulo p)
has
p+1+
solutions (x,y) mod p, where the error  satisfies
  2 p.
- 30 -
Elliptic Curves and
Cryptography
The (Elliptic Curve) Discrete Log Problem
Suppose that you are given two points P and Q in E(Fp).
The Elliptic Curve Discrete Logarithm Problem (ECDLP)
is to find an integer m satisfying
m summands
Q = P + P + … + P = mP.
• If the prime p is large, it is very very difficult to find m.
• Neal Koblitz and Victor Miller (1985) independently
invented Elliptic Curve Cryptography in 1985 when they
suggested building a cryptosystem around the ECDLP.
• The extreme difficulty of the ECDLP yields highly
efficient cryptosystems that are in widespread use
protecting everything from your bank account to your
government’s secrets.
- 32 -
Elliptic Curve Diffie-Hellman Key Exchange
Public Knowledge: A group E(Fp) and a point P of order n.
BOB
ALICE
Choose secret 0 < b < n
Choose secret 0 < a < n
Compute QBob = bP
Compute QAlice = aP
Send QBob
to Bob
Compute bQAlice
to Alice
Send QAlice
Compute aQBob
Bob and Alice have the shared value bQAlice = abP = aQBob
Presumably(?) recovering abP from aP and bP requires
solving the elliptic curve discrete logarithm problem.
- 33 -
Elliptic Curves and
Classical Physics
The Pit and the Pendulum
- 35 -
The Pit and the Pendulum

In freshman physics, one assumes
that  is small and derives the
formula
2
d
2
 k 
2
dt
This leads to a simple harmonic
motion for the pendulum.
But this formula is only a rough approximation. The
actual differential equation for the pendulum is
d2
2


k
sin( )
2
dt
- 36 -
How to Solve the Pendulum Equation
To solve the pendulum equation,

we make the substitution x  tan 
 2  and do a bunch of algebra.
An Elliptic Integral!!!
An Elliptic Curve!!!
As a favor, I’ll spare you the details
and just tell you the answer!!
2kt is equal to

d
dx
dx
 2
 2
y
cos( )
1 x 4
w ith y  1  x .
2
4
Conclusion: tan( /2) = Elliptic Function of t
- 37 -
Elliptic Curves and
Modern Physics
Elliptic Curves and String Theory
In string theory, the notion of a point-like particle is replaced
by a curve-like string.
As a string moves through space-time, it traces out a surface.
For example, a single string that moves around and returns to
its starting position will trace a torus.
So the path traced by a string looks like an elliptic curve!
In quantum theory, physicists like to compute averages over
all possible paths, so when using strings, they need to
compute integrals over the space of all elliptic curves.
- 39 -
Elliptic Curves and
Number Theory
Fermat’s Last Theorem
Fermat’s Last Theorem and Fermat Curves
Fermat’s Last Theorem says that if n > 2, then the equation
an + bn = cn
has no solutions in nonzero integers a,b,c.
It is enough to prove the case that n = 4 (already done by
Fermat himself) and the case that n = p is an odd prime.
If we let x = a/c and y = b/c, then solutions to Fermat’s
equation give rational points on the Fermat curve
xp + yp = 1.
But Fermat’s curve is not an elliptic curve. So how can
elliptic curves be used to study Fermat’s problem?
- 41 -
Elliptic Curves and Fermat’s Last Theorem
Gerhard Frey (and others) suggested using an hypothetical
solution (a,b,c) of Fermat’s equation to “manufacture” an
elliptic curve
Ea,b,c : y2 = x (x – ap) (x + bp).
Frey suggested that Ea,b,c would be such a strange curve, it
shouldn’t exist at all. More precisely, Frey doubted that Ea,b,c
could be modular.
Ribet verified Frey’s intuition by proving that Ea,b,c is indeed
not modular.
Wiles completed the proof of Fermat’s Last Theorem by
showing that (most) elliptic curves, in particular elliptic
curves like Ea,b,c, are modular.
- 42 -
Elliptic Curves and Fermat’s Last Theorem
Ea,b,c : y2 = x (x – ap) (x + bp)
To Summarize:
Suppose that ap + bp = cp with abc  0.
Ribet proved that Ea,b,c is not modular
Wiles proved that Ea,b,c is modular.
Conclusion: The equation ap + bp = cp has no solutions.
But what does it mean
for an elliptic curve E to
be modular?
- 43 -
Elliptic Curves and Modularity
There are many equivalent definitions, all of them
rather complicated and technical. Here’s one:
E is modular if it is parameterized by modular forms!
A modular form is a function f(t) with the property
 at  b 
2
f
  (ct  d ) f (t )
 ct  d 
a b
for all matrices 
 SL 2 (Z) satisfying c  0 (mod N).

c d
The variable t represents the elliptic curve Et whose lattice
is
Lt = {n1+n2t : n1,n2  Z }.
So just as in string theory, the space of all elliptic curves
makes an unexpected appearance.
- 44 -
Conclusion
- 45 -
The Ubiquity of
Elliptic Curves
Joseph Silverman (Brown University)
Public Lecture
Dublin – September 4, 2007