Cryptomathematics and ComputabilityLaajuus (3 ECTS)

Objective

The student is sufficiently familiar with algebraic theories in order to understand the operation of the most usual encryption algorithms and the basis of encryption. The student understands the basic facts of computational complexity such as the difference between polynomial and superpolynomial work of computation and the idea of probabilistic algorithms.

Content

The basic algebraic concepts such as group, ring, and field as well as their basic properties. The difference between private key and public key encryption. The problem of factorization and the algorithm of Rivest-Shamir-Adleman. The prime number test of Miller-Rabin. The problem of discrete logarithm and the algorithm of ElGamal for coset fields and elliptic curves. The problem of quadratic residues and the algorithm of Rabin. The complexity classes P and NP and the idea of probabilistic algorithms.

Qualifications

Sufficient maturity of mathematical abilities to enable abstract thinking.