Course offerings

In this course, we will focus on the computational resources (essentially, the computational time) needed to solve algorithmic problems. In particular, we will try to distinguish between so-called "easy" problems, which can be solved with a reasonable amount of resources (problems whose complexity is a polynomial function of the problem size), and so-called "hard" problems, which are beyond the reach of existing computers.

We will introduce the fundamental complexity classes P and NP and define NP-completeness. Most algorithmic problems encountered in practice are "hard". We will be interested in the trade-offs and relationships between different computational "modes": what happens if we allow ourselves to use probabilistic algorithms, if we are satisfied with approximate rather than exact solutions, if we are satisfied with an algorithm that works only for most but not all possible inputs? This course will introduce techniques of approximation and randomization of algorithms that allow to circumvent the difficulty of solving hard problems, and thus allow their use in practice with reasonable computation times. These techniques will be illustrated in tutorials and in lab-projects on a range of concrete problems from the various specialties of the master.

• Model of a computer; Turing machines.
• Complexity classes and reductions.
• Tree methods.
• Approximation algorithms with performance guarantee.
• Probabilistic algorithms (Las Vegas, Monte Carlo)
• Probabilistic graph algorithms.
• Probabilistic algebraic algorithms (primality tests; polynomial identity tests).
• Probabilistic algorithms for variants of the SAT problem.
• Probabilistic complexity classes (BPP, ZPP, RP, PP)

Evaluation: Small project (20%), Mid-term exam (40%), Final exam (40%)

The course provides an introduction to fundamental linear algebra algorithms with approximate or exact computation. Classical techniques, like Gaussian elimination, least-square approximation, SVD, FFT, are studied together with dedicated methods to sparse and structured linear systems using algebraic modeling. In-depth complexity analyses of naive and more advanced algorithms are also studied.

This finds applications in many areas of computer science (cryptography, high-performance computing, big data, operational research, imagery, etc.).

• Exact and approximate linear system solving
• SVD and FFT
• Complexity and non-naive multiplication algorithms for integers, polynomials and matrices
• Reductions to matrix multiplication, structured and sparse linear system solving
• Evaluation: Quizzes (20%), Small project (20%), Mid-term exam (30%), Final exam (30%)

Large-scale computations require both a massive amount of computing hardware, which is thus necessarily parallel, and programmers with a specific training to exploit it.  This course introduces students to the industry-standard tools and techniques  used in High-Performance Computing using the C programming language. It presents message-passing programming of computer clusters using MPI libraries, multi-thread programming of multi-core CPUs using OpenMP and vectorization (the exploitation of SIMD instructions in contemporary CPUs). In addition, the courses discusses algorithmic issues in parallel programming (how to do THAT in parallel?), how low-level hardware issues (cache, paging, branch prediction, ...) affect  performance and to to maneuver around them. Finally, the course presents performance models as well as techniques to understand and anticipate the running-time of actual parallel programs.

Evaluation: two large parallelization projects (33% each), final exam (33%).

This course is the natural continuation of the numerical part of MODEL course. It is a question of supplementing the knowledge in mathematical tools and algorithms in order to be able to solve concrete problems and of large sizes. We will study in particular algorithms and their implementation frequently used in the field of scientific computing and data science. The applications will be very diverse and may change each year: for example, we will see applications in finance (calculation of the price of options), in simulation of structures for 3D printing, in imaging (image compression), in deep learning (stochastic gradient algorithm), etc. We will endeavor for each algorithm to propose versions allowing an efficient implementation on parallel machines. The algorithms will be coded in MATLAB.

– Floating-point arithmetic and rouding error analysis

– Matrix computation

– Introduction to continuous optimization

– Interpolation and approximation

– Numerical differentiation et integration

– Monte Carlo method

Grades will be computed as follows: exam 1 (40%), exam 2 (40%), praticals (20%).

In this course, we study fundamental algorithms for efficient computations with algebraic objects such as matrices and polynomials which arise frequently in cryptography and high-performance computing . We tackle basic operations in finite fields, computations with polynomials and formal power series, linear algebra operations, structured linear system solving, and polynomial system solving in two variables. We conclude the course with an introduction to Reed-Solomon error correcting codes and some of their decoding algorithms. Coding theory is one of the natural fields of application of the notions studied in the course, which are at the core of computer algebra and also central in various areas of cryptology.

Evaluation : tests (30%), project (35%), final exam (35%)

This course presents the basics of modern cryptology: encryption, digital signature, etc. These techniques guarantee the confidentiality and integrity of day-to-day online communications. On the menu: symmetric ("secret key") encryption, block ciphers, overview of the AES, operating modes for encryption, cryptographic hash functions. Public key cryptography: presentation of RSA encryption and signature, discussion of large integer factorization algorithms. Introduction to the discrete logarithm problem and its applications (Elgamal encryption, DSA signature, ...). Description of the TLS and SSH protocols that combine all the above. The course concludes with a multi-week cryptanalysis sequence, including the presentation of significant attacks, notably based on the use of Euclidean networks.

Evaluation : midterm + final exam (33% each) + online practical work (33%)

This course is at the intersection of algorithmic and mathematics. One of the goals is to master the concepts related to rounding errors and their consequences as well as learning how to perform an analysis of the numerical quality of scientific code. We will present the floating-point arithmetic (IEEE 754 standard) and its consequences for numerical results of scientific computing codes as well as theory and practice of methods of estimating or increasing the accuracy of computed results in general using in particular interval arithmetic, discrete stochastic arithmetic and compensated methods. A presentation of the theory for computing elementary functions will also be proposed.

Two thirds of this course are dedicated to CUDA programming (Part I). One third of this course is dedicated to large problems solving with multi-node architecture (Part II).

This Part I introduces GPU programming using CUDA API and then provides a large number of examples that will make the reader more and more comfortable with the hardware and the API used. The purpose is to give the technical background that opens scaling up applications to a large public of students, researchers, and engineers.

Modern computers have an increasing number of computing units. To take advantage of this parallelism, it is therefore necessary to use and implement algorithms with a high level of concurrency. In this Part II, different techniques for solving hollow linear systems that benefit from such a feature are presented. In particular, domain decomposition methods and multigrid methods that have an optimal asymptotic cost are detailed.

Here is a link to the detailed syllabus

Systems of polynomial equations encode a wide variety of problems in engineering and computing sciences such as robotics and cryptography since they easily encode Euclidean geometric and arithmetic properties. Their use in cryptography, for designing post-quantum encryption and signature schemes is motivated by the NP-hardness of solving systems of polynomial equations.

This course focuses on algebraic methods for solving such systems of equations with a view towards applications in post-quantum cryptography and algebraic cryptanalysis.

A first period is devoted to introduce basic notions and Buchberger-style algorithms, introducing Gröbner bases and their properties. A second period is devoted to techniques for analyzing the complexity of Gröbner basis algorithms. A third period introduces linear algebra-based Gröbner bases algorithms. The last period covers applications in post-quantum cryptography.

Exercise sessions are scheduled and computer sessions organized in order to help the student to better assimilate the contents of the course.

L’UE SCA (Side-Channel Attacks) s’intéresse à toutes les attaques par canaux auxiliaires d’implémentations d’algorithmes cryptographiques, et plus particulièrement de l’AES, qui constitue un fil rouge pour le module. Les principaux types d’attaques considérés sont les attaques par analyse de consommation et les attaques par faute. Les attaques de Timing sont également abordées en cours. L’UE accorde une place importante aux travaux pratiques (28h), qui sont complétés par 20h de cours.

Les thèmes abordés en cours sont les suivants :

– Sécurité embarquée et attaques matérielles

– Attaques par analyse de consommation

– Attaques par faute

– Attaque par analyse de timing

– Contre-mesures logicielles face aux attaques

– Évaluation de fuites secrètes

Les travaux pratiques comprennent les points suivants :

– Analyse de traces de consommation, lien entre consommation et instructions exécutées

– Attaque d’un code (récupération d’un mot de passe) par analyse simple de consommation

– Lien entre consommation et données manipulées par un programme

– Attaque de l’AES par analyse différentielle de la consommation

– Implantation d’un schéma de protection pour l’AES

– Attaques par faute sur simulateur

Evaluation : 50% pour les TPs et 50% par un examen.

Ce cours de cryptographie explore les concepts, protocoles et techniques plus avancés dans le domaine de la sécurité de l’information, en étudiant des résultats récents de cryptographie classique et post-quantique. Il présente notamment les signatures numériques et les preuves à divulgation nulle de connaissance, le calcul réparti sécurisé, les signatures fondées sur le calcul réparti sécurisé « dans la tête », la cryptanalyse fondée sur les réseaux euclidiens, des algorithmes de chiffrement par blocs et leurs techniques de cryptanalyse, et une introduction à la cryptographie post-quantique.

Volume horaire : 18h CM, 18h TD, 18h TP

Modalités d’évaluation : deux examens répartis (un « partiel » + un « final ») et une note de TP, qui comptent pour 35%, 35% et 30% respectivement. Les TME ont lieu en-ligne sur une plate-forme que nous avons développée.