Learning objectives
The basic ideas of modern cryptogtraphy
Prerequisites
Basic Algebra, basic calculus
Course unit content
1. Overview of the theory of finite groups and finite fields
Theorems of Fermat, Euler and Wilson, structure of the ring Z/pZ, p prime.
Gauss's Theorem: existence of primitive roots (generators) in the groups (Z/pZ)*, p prime.
Necessary and sufficient conditions for primality. Fermat, Euler, and strong pseudoprimes.
Sketch of the proof of the Theorem of Agrawal, Kayal, Saxena.
2. Basic algorithms
Euclid's algorithm, Eratosthenes' sieve, primality tests.
Exponential factorization algorithms: trial division, Lehman's method, Pollard's ρ method, Pollard's p − 1 method.
Subexponential factorization algorithms: the quadratic sieve.
Gauss's algorithm for the computation of primitive roots.
Discrete logarithm: the Silver–Pohlig–Hellman algorithm, the Shanks algorithm (“baby steps, giant steps”).
3. Applications to cryptography
Some remarks on classical cryptography.
Public key cryptography: the Diffie–Hellman, RSA, Massey–Omura, ElGamal, Rabin cryptosystems.
Digital signature.
Cryptographic protocols.
Full programme
- - -
Bibliography
1. R. CRANDALL & C. POMERANCE, Prime numbers. A computational perspective, Springer, New York, 2001.
2. G. H. HARDY & E. M. WRIGHT, An Introduction to the Theory of Numbers, Oxford Science Publications, Oxford, 1979.
3. N. KOBLITZ, A Course in Number Theory and Cryptography, Springer, 1994.
4. A. LANGUASCO & A. ZACCAGNINI, Manuale di crittografia, Ulrico Hoepli Editore, Milano, 2015.
Teaching methods
Traditional lecture, with slides
Assessment methods and criteria
Seminar or project, chosen with the help of the teacher
Other information
- - -
