Learning objectives
# <br />
These correspond with the programme
Prerequisites
# <br />
Algebra, Functions of one variable 1
Course unit content
<br />1. References to the theory of groups and of finite fields <br />
* Theorems of Fermat, Euler and Wilson, structure of theZ/pZring, prime p. <br />
* Theorem of Gauss: existence of primitive roots (generators) of groups (Z/pZ)*, prime p. <br />
* Necessary and sufficient conditions for primality. Fermat pseudoprimes, Euler pseudoprimes, strong pseudoprimes. <br />
* A mention of the Theorem of Agrawal, Kayal, Saxena. <br />
2. Fundamental algorithms <br />
* Euclid's algorithm, sieve of Eratosthenes, primality tests. <br />
* Exponential factoring algorithms: trial division, Lehman method, Pollard ñ method, Pollard p - 1 method. <br />
* Subexponential factoring algorithms: quadratic sieve. <br />
* Gauss algorithm for calculating primitive roots. <br />
* Discrete logarithm: Silver-Pohlig-Hellman algorithm, Shanks algorithm. <br />
3. Applications to cryptography <br />
* References to classical cryptography. <br />
* Public key cryptography: Diffie-Hellman, RSA, Massey-Omura, ElGamal, Rabin cryptosystems. <br />
* Digital signature. <br />
* Cryptographic protocols (notes).
Full programme
- - -
Bibliography
1. R. CRANDALL & C. POMERANCE,Prime numbers. A computational perspective, Springer, New York, 2001. <br />
2. G. H. HARDY & E. M. WRIGHT,An Introduction to the Theory of Numbers, fifth edition, Oxford Science Publications, Oxford, 1979. <br />
3. N. KOBLITZ, A Course in Number Theory and Cryptography, second edition, Springer, 1994. <br />
4. A. LANGUASCO & A. ZACCAGNINI,Introduzione alla crittografia,Ulrico Hoepli Editore, Milano, 2004.
Teaching methods
The student may choose from a traditional oral exam, a seminar on a cryptographic topic or a small data processing project applied to cryptography
Assessment methods and criteria
- - -
Other information
- - -
