IMPORTANT: The following syllabus provides a high-level description of the course topics. Students should consult the lectures diary for a detailed description of the topics covered in each lecture

  1. NP-Completeness. Reduction Techniques. Complexity Classes.

  2. Approximation algorithms for intractable problems.

  3. Number-theoretic algorithms and cryptographic applications of intractability: greatest common divisor, modular aritmethix, Miller-Rabin primality testing, RSA cryptosystem.

  4. Randomized algorithms: main techniques and applications.

Last update: September 10, 2021 Go to index