This course is a prerequisite for all theory courses as well as Introduction to Security (Part IB), Artificial Intelligence I and II, Information Theory and Coding (Part II), Security (Part II).
Aims
This course will develop the idea of formal proof by way of examples
involving simple objects such as integers and sets. The material
enables academic study of Computer Science and will be promoted with
examples from cryptography and the analysis of algorithms.
Factors.
Division: highest common factors and least common multiples. Euclid's
algorithm: solution in integers of , the
complexity of Euclid's algorithm. Euclid's proof of the infinity of
primes. Existence and uniqueness of prime factorisation.
Irrationality of . [3 lectures]
Modular arithmetic.
Congruences. Units modulo m, Euler's totient function.
Chinese remainder theorem. Wilson's theorem. The Fermat-Euler
theorems, testing for primes. Public key cryptography, Diffie-Hellman and RSA. [3 lectures]
Objectives
On completing the course, students should be able to
write a clear statement of a problem as a theorem in mathematical
notation; prove and disprove assertions using a variety of techniques
describe, analyse and use Euclid's algorithm;
explain and apply prime factorisation
perform calculations with modular arithmetic;
use number theory to explain public key cryptography
Recommended books
* Humphreys, J.F. & Prest, M.Y. (1989). Numbers, groups and codes. Cambridge University Press.
Biggs, N.L. (1989). Discrete mathematics. Oxford University Press.
Conway, J.H. & Guy, R.K. (1996). The book of numbers. Springer-Verlag.
Davenport, H. (1992). The higher arithmetic. Cambridge University Press (6th ed.).
Giblin, P. (1993). Primes and programming. Cambridge University Press.
Pólya, G. (1980). How to solve it. Penguin.