The following syllabus provides a high-level description of the course topics. Students should consult the
for a detailed description of the topics covered in each lecture
NP-Completeness. Reduction Techniques. Complexity Classes.
Approximation algorithms for intractable problems.
Number-theoretic algorithms and cryptographic applications of intractability: greatest common divisor, modular aritmethix, Miller-Rabin primality testing, RSA cryptosystem.
Randomized algorithms: main techniques and applications.
Last update: September 10, 2021
Go to index