Learning objectives
The theory behind cryptography and some applications
Prerequisites
Basic calculus, basic algebra
Course unit content
Overview of the theory of finite groups and finite fields
Fundamental algorithms
Applications to cryptography
Cryptographic protocols.
Full programme
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.
Fundamental 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”).
Applications to cryptography
Some remarks on classical cryptography.
Public key cryptography: the Diffie–Hellman, RSA, Massey–Omura, ElGamal, Rabin cryptosystems.
Digital signature.
Cryptographic protocols.
Bibliography
R. CRANDALL & C. POMERANCE, Prime numbers. A computational perspective, Springer, New York, 2001.
G. H. HARDY & E. M. WRIGHT, An Introduction to the Theory of Numbers, quinta edizione, Oxford Science Publications, Oxford, 1979.
N. KOBLITZ, A Course in Number Theory and Cryptography, seconda edizione, Springer, 1994.
A. LANGUASCO & A. ZACCAGNINI, Manuale di crittografia, Ulrico Hoepli Editore, Milano, 2015.
Teaching methods
Traditional lectures
Assessment methods and criteria
Lecture given by the student on a topic agrred upon with the lecturer
Other information
- - -
