Number Theory and Cryptography

• Credit value: 30 credits at Level 5
• Convenor and tutor: Professor Maura Paterson
• Assessment: two problem sets (10% each), an untimed quiz (10%) and a three-hour examination (70%)

In the first half of this module we study number theory, with particular emphasis on prime numbers and their properties. Then, in the second half we explore various cryptographic techniques that have been used from antiquity to the present day, making use of parts of the number theory studied in the first term.

Indicative syllabus

Number Theory

• Modular arithmetic: linear congruences, the Euclidean algorithm, Fermat's little theorem, Euler's theorem, the Chinese Remainder theorem, the square-and-multiply algorithm, primitive elements, Fermat primes, Mersenne primes, perfect numbers
• Number-theoretic functions, including Euler's totient function
• Quadratic congruences, quadratic residues, the Legendre symbol, quadratic reciprocity, the Jacobi symbol, primality testing

Cryptography

• Symmetric cryptosystems: historical ciphers, the Vernam cipher, block ciphers
• Public key encryption: RSA encryption, security of public key encryption schemes, the Rabin cryptosystem
• Signature schemes: definition of a digital signature, RSA signatures, security of signature schemes, hash functions and signatures

By the end of this module, you will be able to:

• use mathematical and/or statistical techniques
• understand a range of results in mathematics
• appreciate the need for proof in mathematics, and follow and construct mathematical arguments
• appreciate the power of generalisation and abstraction in the development of mathematical theories
• show a deeper knowledge of particular areas of mathematics, specifically definitions, techniques and results from number theory, along with a knowledge of common encryption algorithms that have been used over time.