cod. 1005700

Academic year 2015/16
3° year of course - First semester
Academic discipline
Analisi matematica (MAT/05)
Attività formative affini o integrative
Type of training activity
48 hours
of face-to-face activities
6 credits
hub: PARMA
course unit
in - - -

Learning objectives

Theoretical basis for cryptography. Detailed description of cryptographic systems. Algorithms. The student should be aware of the different aspects of cryptography and of the numerous fields of applications


Basic algebra. Basic calculus

Course unit content

Algebraic foundations of cryptography. Cryptographic methods and protocols. Algorithms

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.


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, quinta edizione, Oxford Science Publications, Oxford, 1979.
3. N. KOBLITZ, A Course in Number Theory and Cryptography, seconda edizione, Springer, 1994.
4. A. LANGUASCO & A. ZACCAGNINI, Introduzione alla crittografia, Ulrico Hoepli Editore, Milano, 2004.

Teaching methods

Classical-style lecture

Assessment methods and criteria

The student will give a lecture on a topic chosen from the program, and answers questions on the whole program, in order to ensure that the student has actually acquired a working knowledge of the critical aspects of cryptography recalled above

Other information

- - -