Aims

To present some of the classical results in Number Theory. To provide an understanding of the mathematical principles underlying encryption and cryptanalysis in the military, diplomatic and commercial domains. To show how Number Theory and Group Theory play an important role in communication in the modern world.

Module Summary

The more one examines the properties and inter-relationships of the numbers 1,2,3,4,5,... the more interesting they become. The early Greeks knew about primes and perfect numbers. Since those days many of the most famous mathematicians have worked hard to prove results about the natural numbers, and while doing so have invented techniques and crystallized definitions that have influenced the development of many branches of pure mathematics. Results in number theory are often easy to understand and state, for example "find a formula for the number pi(x) of primes less than x, or at least a good approximation (the prime number theorem)", or "the probability that two positive integers are relatively prime is 6/pi ^2 ".

Security, confidentiality and authentication are of great significance in the age of electronic communication. Cryptography is the means of achieving these aims. We shall look at some of the fundamental symmetric ciphers, these are fast and efficient to implement but have a weakness in that both parties need to know the key. We shall study code-breaking techniques for such ciphers and see how ways of combining ciphers reduces vulnerability to such techniques. We shall look at public key cryptography (asymmetric ciphers), where anyone can encipher a message but only the key holder can decipher it. Such ciphers are relatively slow but avoid the need for a key to be exchanged between the parties. In practice, public key cryptography can be used to transmit the key of a good symmetric cipher, so both symmetric and asymmetric ciphers play important roles. We shall look at the idea of a digital signature, a means of verifying the identity of the sender of an electronic message. Most ciphers are based on mathematical constructions from Number Theory, Group Theory and Geometry. We shall concentrate largely on applications of Number Theory. We shall use a few ideas from Group Theory but no prior knowledge is necessary.

Outline Of Syllabus

Congruence arithmetic. The Chinese Remainder Theorem for simultaneous congruence equations. The divisor, sum, Mobius and Euler totient functions and their properties. Lagrange's Theorem. The roots of x^d-1 modulo a prime. Dirichlet series, their multiplication and use as generating functions. Infinite-product expansions. The Riemann zeta function. Quadratic residues. Gauss' Law of Reciprocity. There will be considerable emphasis on the applications and use of the theorems.

Modular arithmetic and finite fields. Symmetric ciphers: permutation, affine and matrix ciphers. Public key cryptography: key exchange protocols, asymmetric ciphers (particularly RSA), authentication. Primality testing and factorisation techniques.

Teaching Rationale And Relationship

The teaching methods are appropriate to allow students to develop a wide range of skills, from understanding basic concepts and facts to higher-order thinking.

Lectures are used for the delivery of theory and explanation of methods, illustrated with examples, and for giving general feedback on marked work. Problem Classes are used to help develop the students’ abilities at applying the theory to solving problems.

Assessment Rationale And Relationship

A substantial formal unseen examination is appropriate for the assessment of the material in this module. The format of the examination will enable students to reliably demonstrate their own knowledge, understanding and application of learning outcomes. The assurance of academic integrity forms a necessary part of the programme accreditation.

Examination problems may require a synthesis of concepts and strategies from different sections, while they may have more than one ways for solution. The examination time allows the students to test different strategies, work out examples and gather evidence for deciding on an effective strategy, while carefully articulating their ideas and explicitly citing the theory they are using.

The coursework assignments allow the students to develop their problem solving techniques, to practise the methods learnt in the module, to assess their progress and to receive feedback; these assessments have a secondary formative purpose as well as their primary summative purpose.