Number Theory and Cryptography

• Credit value: 30 credits at Level 5
• Convenor and tutor: Maura Paterson
• Assessment: short, problem-based assignments (20%) and a three-hour examination (80%)

In the first half of this module we will study number theory, with particular emphasis on prime number 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 module 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 have:

• knowledge and understanding of, and the ability to use, mathematical and/or statistical techniques
• knowledge and understanding of a range of results in mathematics
• an appreciation of the need for proof in mathematics, and the ability to follow and construct mathematical arguments
• an ability to present, analyse and interpret data
• an appreciation of the power of generalisation and abstraction in the development of mathematical theories
• a deeper knowledge of some 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
• an ability to use a modern mathematical and/or statistical computer package with a programming facility, together with knowledge of other suitable packages
• an appreciation of the historical and cultural aspects of mathematics.