1. komponenta

Lecture type	Total

* Load is given in academic hour (1 academic hour = 45 minutes)

COURSE AIMS AND OBJECTIVES: Enable students to:
- understanding the role of number theory in modern computer cryptography;
- application and implementation of algorithms for solving problems with congruences, primality testing and factorization of large integers.

COURSE DESCRIPTION AND SYLLABUS:
1. Basic algorithms in number theory. Algorithms for multiplying large integers. Euclidean algorithm. Chinese remainder theorem. Continued fractions. Quadratic congruences. Squares and square roots. LLL algorithm.
2. Public key cryptography. Cryptosystems based on the problem of factorization. Cryptosystems based on the discrete logarithm problem. Other public key cryptosystems. Application of LLL-algorithm in cryptanalysis.
3. Testing and proving primality. Distribution of prime numbers. Pseudoprime numbers. Miller-Rabin, AKS and other primality tests.
4. Factorization methods. Pollard ro-method. Pollard p-1 method. Continued fraction method. Quadratic sieve method.