Teachers: Xavier Caruso and Jean-Marc Couveignes
Program:
In this lecture we will discuss several aspects of algorithmic number theory closely related to cryptography.
The course will be organized as follows: in the first part we will discuss classical algorithms for primality and factorisation. The second part will be an introduction to quantum algorithms, in view of a discussion of Shor quantum algorithm for factorization and discrete log problem, which is of (quantum) polynomial complexity. In the third part, we will discuss Euclidean lattices, and their recent applications to cryptography that (conjecturally) resist quantum algorithms.
The lectures will be illustrated by programming sessions using SAGE.
Prerequisites:
There are no prerequisites for this course other than a few elementary notions of arithmetic and algebra (rings, ideals, bilinear algebra, etc.).
Part of the course will be taught in the computer room using the
SageMath mathematical software system, but it is not necessary to be familiar with this system before.
Bibliography:
J. von zur Gathen and J. Gerhard: Modern computer algebra, Cambridge University Press, New York, 1999.
A. M. Childs and W. van Dam: Quantum algorithms for algebraic problems, Reviews of Modern Physics, 2010
C. Peikert: A decade of lattice cryptography, 2016, available at http://web.eecs.umich.edu/ cpeikert/#research