This course presents the basic algorithms from number theory that are of major importance for public key cryptography.
This will include fundamentals from complexity theory, elementary computer arithmetics, algorithms for integers and congruences, introduction to elliptic curves, ... , and an introduction to computational problems such as integer factoring and computing discrete logarithms that play a crucial role in this field.
The classical computational models (Turing machines) and the Quantum computer point of vue will both be presented.
Lectures will be given by Xavier Caruso (quantum algorithmics) and Jean-Marc Couveignes (classical algorithmics).
They will take place in a classroom or in a computer room alternately. We will use the sagemath computer algebra system.
You will work in pairs during the computer sessions. At the very end of the semester every pair will send an account of all the work done during the computer sessions. We do not ask for a full report : just a brief description. This work will be evaluated and will account for one third of the assessment.
There will be a written, 3 hours long, final examination. This final examination will account for two thirds of the assessment.
- Enseignant: Xavier Caruso
- Enseignant: Jean-Marc Couveignes