Croatian

Andrej Dujella:

Algorithms for elliptic curves

Graduate course     (2008/2009)

Course description

This course will cover some important algorithms for elliptic curves over the field of rational numbers and over finite fields.

We will describe in details the algorithms for obtaining information on Mordell-Weil group of an elliptic curve of the field of rationals (torsion group, upper and lower bounds for the rank, generators in case when the rank can be computed exactly). Some methods for construction of high rank elliptic curves will be described, and also methods for finding all integer points on elliptic curves, in particular, the methods based on the knowledge of the associated Mordell-Weil group.

Concerning elliptic curves of finite fields, we will discuss efficient implementation of point addition and multiplication, with special emphasis on field of characteristic 2, which are important for applications in cryptography. Algorithms for point counting and elliptic curve discrete logarithm problem will be described.

It is expected that this course will make the students competent for using programs and program packages specialized for work with elliptic curves (PARI/GP, MWRANK, MAGMA), and they will use them in solving exercises.

It will be assumed that the students are familiar with the basic notions and results on elliptic curves, at the level covered in the graduate course Ivica Gusić: Introduction to Arithmetic of Elliptic Curves (lecture notes (in Croatian) can be found on http://www.math.hr/~duje/seminar.html) or the standard textbook Silverman, Tate: Rational Points on Elliptic Curves.


References

  1. I. Blake, G. Seroussi, N. Smart: Elliptic Curves in Cryptography, Cambridge University Press, Cambridge, 1999.

  2. H. Cohen: A Course in Computational Algebraic Number Theory, Springer-Verlag, New York, 1993.

  3. H. Cohen: Number Theory. Volume I: Tools and Diophantine Equations, Springer Verlag, Berlin, 2007.

  4. I. Connell: Elliptic Curve Handbook, McGill University, 1999.

  5. J. E. Cremona: Algorithms for Modular Elliptic Curves, Cambridge University Press, Cambridge, 1997.

  6. A. Dujella, M. Maretić: Kriptografija, Element, Zagreb, 2007.

  7. D. Hankerson, A. Menezes, S. Vanstone: Guide to Elliptic Curve Cryptography, Springer-Verlag, New York, 2004.

  8. S. Schmitt, H.G. Zimmer: Elliptic Curves. A Computational Approach, de Gruyter, Berlin, 2003.

  9. J. H. Silverman: Elliptic curves and cryptography, in: P. Garrett, D. Lieman (Eds.): Public-Key Cryptography, American Mathematical Society, Providence, 2005, pp. 91-112.

  10. J.H. Silverman: The Arithmetic of Elliptic Curves, Springer-Verlag, 1996, 2009.

  11. J. H. Silverman, J. Tate: Rational Points on Elliptic Curves, Springer-Verlag, Berlin, 1992.

  12. N. P. Smart: The Algorithmic Resolution of Diophantine Equations, Cambridge University Press, Cambridge, 1998.

  13. L. C. Washington: Elliptic Curves: Number Theory and Cryptography, CRC Press, Boca Raton, 2003, 2008.

Lecture notes
(in pdf format; in Croatian)


Seminar topics


Homework exercises:

ex1   ex2   ex3


Some (useful) links

Seminar on Number Theory and Algebra (University of Zagreb)
Number Theory - Undergraduate course (Andrej Dujella)
Cryptography - Undergraduate course (Andrej Dujella)
Elliptic curves and their applications in cryptography - Student seminar (2002/2003)
Number Theory in Cryptography - Graduate course (Andrej Dujella, 2003/2004)
Diophantine Equations - Graduate course (Andrej Dujella, 2006/2007)
Algorithms from A Course in Computational Algebraic Number Theory (James Pate Williams)
Software packages of interest to number theory
PARI/GP home page
SAGE home page
Cremona's MWRANK
Algorithmic Number Theory: Tables and Links (Noam Elkies)
High rank elliptic curves with prescribed torsion (Andrej Dujella)
Number Theory Web (maintained by Keith Matthews)
Recommended readings for graduate students in number theory

Web pages of some courses on elliptic curves:

Algorithmic Aspects of Elliptic Curves (Andrej Dujella)
Arithmetic of Elliptic Curves and Modular Forms (Hossein Movasati)
Elliptic Curves (Edray Goins)
Elliptic Curves (Jim Milne)
Elliptic Curves (Miles Reid)
Elliptic Curves (Helena Verrill)
Elliptic Curves and Applications (Andrej Dujella)
Elliptic Curves and Cryptography (Alan Silvester)
Elliptische Kurven (Franz Lemmermeyer)
Introduction to elliptic curves (Ian Kiming)
Number Theory of Cubic Curves (Jaap Top)
Rational Points on Elliptic Curves (Daniel Rogalski)
Selected Topics in Number Theory (Jerrold Tunnell)
Vorlesung uber Elliptische Kurven und Kryptographie (Wolfgang Ruppert)

Andrej Dujella home page