cod. 1005700

Academic year 2023/24
1° year of course - First semester
- Alessandro ZACCAGNINI
Academic discipline
Analisi matematica (MAT/05)
Attività formative affini o integrative
Type of training activity
48 hours
of face-to-face activities
6 credits
course unit

Learning objectives

The theory behind cryptography and some applications


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.


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

- - -