Elliptic Curves (Spring semester 2005)
Organization
Instructors
- H.W. Lenstra, Mathematisch Instituut, Leiden, e-mail: hwl {at} math.leidenuniv.nl
- W.B. Hart, Mathematisch Instituut, Leiden, e-mail: wbhart {at} math.leidenuniv.nl"
- W.H. Ekkelkamp, CWI, Amsterdam / Mathematisch Instituut, Leiden, e-mail: W.H.Ekkelkamp {at} cwi.nl
Lectures
The lectures will be given on Monday morning from 10:15 until 13:00. The place to be is:
Vrije Universiteit
De Boelelaan 1083
Amsterdam
Mathematics & Sciences building (WG)
Room S209
Click here for a route description and a map of the campus. Courses are given in building 4 on the map.
The lectures start on February 7, the last lecture is on May 30. There will be no lecture on: March 28, May 16.
Attending this course will be rewarded with 8 EC points.
Registration
Registration for this course is obligatory. See 'Registration' on this page.
Course information
Description
The main subject of the course is the arithmetic of elliptic curves. An elliptic curve may be defined as a plane non-singular cubic curve together with a point lying on the curve. We shall mainly be concerned with elliptic curves that are defined over fields of arithmetic interest, such as algebraic number fields and finite fields. Algorithmic issues and applications of elliptic curves will receive particular attention.
Prerequisites
Prerequisites for the course include mathematical maturity appropriate for an advanced course, and knowledge of basic algebra as taught during the first three years. The course notes in Dutch used in Leiden-Delft can be found here. For an english version take, e.g., S. Lang, Algebra, Springer-Verlag. Familiarity with algebraic number theory is helpful. Students who are not acquainted with algebraic geometry are encouraged to take the parallel course taught by Prof. Edixhoven.
Literature
We will use parts of the following books:
- J.H. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag
- J.W.S. Cassels, Lectures on Elliptic Curves, Cambridge University
Press
- J.H. Silverman & J. Tate, Rational Points on Elliptic Curves, Springer-Verlag
The first book of J.H. Silverman is recommended, but the other two books require less prerequisites.
Other books about elliptic curves are:
- L.C. Washington, Elliptic Curves, Number Theory and Cryptography, Chapman & Hall/CRC
- S. Lang, Elliptic Curves: Diophantine Analysis, Springer-Verlag
- A.J. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers
- I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, Cambridge University Press
- A.W. Knapp, Elliptic Curves, Princeton University Press
The book by Washington is completely low-brow. Lang treats the arithmetic theory from an analytic perspective. Menezes and Blake et al. are concerned with the application of elliptic curves to cryptography. Knapp treats the connection with modular forms.
Some books on category theory are:
- H. Herrlich, G.E. Strecker, Category Theory, Allyn and Bacon
- S. Mac Lane, Categories for the Working Mathematician, Springer-Verlag
Some other useful books:
- H. Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag
- R. Hartshorne, Algebraic Geometry, Springer-Verlag
- N. Koblitz, Introduction to Elliptic Curves and Modular Forms, Springer-Verlag
Stichtenoth contains many details on function fields, which form the algebraic
basis for the theory to be developed in class; Hartshorne is our reference for the definitions needed from algebraic geometry; and Koblitz contains a first introduction to a subject that we will not have time for: the connection between elliptic curves and modular forms, which is at the basis of much modern work, including the proof of Fermat's Last Theorem.
A book on commutative algebra:
- M.F. Atiyah, I.G. MacDonald, Introduction to Commutative Algebra, Addison-Wesley Publishing Company
Literature on Kähler differentials:
- R. Hartshorne, Algebraic Geometry, (Ch. II, § 8)
- H. Matsumura, Commutative Algebra, Benjamin
The following modern book has a lot of overlap with the class. It attempts to do justice both to the geometry and to the algebra:
- D. Lorenzini, An invitation to arithmetic geometry, American Mathematical Society, 1996
Examination
Each week there will be some serious homework assignments. The final grade is exclusively based on the results obtained for these assignments.
Guest Speakers
On March 7 Gadiel Seroussi (Hewlett-Packard Laboratories, Palo Alto) will give a lecture on algorithmic issues in elliptic curve cryptography.
Abstract (Algorithmic issues in elliptic curve cryptography)
Elliptic curve (EC) public key cryptosystems were proposed
independently in 1985 by Victor Miller and Neal Koblitz, and
are considered an efficient and attractive alternative
to the more conventional public key cryptosystems (e.g., RSA)
in some applications.
The security of EC cryptosystems is based on the difficulty of
computing discrete logarithms in a suitable chosen subgroup of
the group of rational points of an elliptic curve over a finite
field. The complexity of the best known algorithms for this problem
is exponential in the size of the field elements, as opposed to the
sub-exponential complexity of the problems underlying conventional
public key cryptography. Due to this complexity gap, EC cryptosystems
can use much shorter keys, which in turn translate, in practice, to
savings in running time, power consumption, silicon area, etc.
A crucial issue in the design of effective EC cryptosystems is the
``point counting problem'', i.e., the precise determination of the
number of rational points on a randomly chosen elliptic curve over
a finite field.
In this presentation, we survey the mathematical and practical
challenges one faces when designing and implementing an
EC cryptosystem.
On April 11 Prof. Bas Edixhoven will give a lecture. The title is: What did Wiles prove?
On May 23 Reinier Bröker (University of Leiden) will give a lecture on point counting algorithms.
Abstract (Point Counting algorithms)
Given an elliptic curve E over a finite field F, a natural question is to
ask for the number of F-rational points of E. This can in principle be computed
by evaluating a lot of Legrende symbols, but this leads to an algorithm
which is exponential in the input size. Large finite fields (with more
than 1020 elements say) are therefore out of reach. In 1984 the Dutch
mathematician René Schoof discovered a polynomial time algorithm. After
some improvements of a more practical nature, it is now possible to
solve the problem for much larger finite fields F. The underlying mathematics
of the algorithm contains e.g. the interplay between curves over finite
fields and over number fields and some algebraic number theory. In this
lecture we will discuss Schoof's algorithm and its improvements.
Course notes
- Course notes in Dutch about categories and tensor products can be found here.
- The course notes can be found here.
Exercises
Each week four exercises out of nine have to be handed in, preferably in english. This can be done by email or handwritten. Of course, you may hand in more than four exercises.
In case of email: send your file in standard latex (.tex) or preferably .ps or .pdf format to both W.B. Hart and W.H. Ekkelkamp. (Latex files which do not compile will not be marked.)
In case of handwritten: hand it in during the next lecture, but make sure that each exercise starts on a new sheet.
In both cases: the deadline is next week's lecture!
It is no problem if students work together, but we don't accept exact copies. Formulate the solution in your own words!