Global Opportunities

MAS3707 : Number Theory and Cryptography

Semesters
Semester 1 Credit Value: 10
Semester 2 Credit Value: 10
ECTS Credits: 10.0

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 Methods

Teaching Activities
Category Activity Number Length Student Hours Comment
Scheduled Learning And Teaching ActivitiesLecture41:004:00Revision Lectures – Present in Person
Scheduled Learning And Teaching ActivitiesLecture101:0010:00Problem Classes – Synchronous On-Line
Guided Independent StudyAssessment preparation and completion301:0030:00Completion of in course assessments
Scheduled Learning And Teaching ActivitiesLecture401:0040:00Formal Lectures – Present in Person
Guided Independent StudyIndependent study1161:00116:00Preparation time for lectures, background reading, coursework review
Total200:00
Jointly Taught With
Code Title
MAS8707Number Theory & Cryptography
Teaching Rationale And Relationship

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 Methods

The format of resits will be determined by the Board of Examiners

Exams
Description Length Semester When Set Percentage Comment
Written Examination1502A80N/A
Exam Pairings
Module Code Module Title Semester Comment
MAS8707Number Theory & Cryptography2N/A
Other Assessment
Description Semester When Set Percentage Comment
Prob solv exercises1M10Coursework assignment
Prob solv exercises2M10Coursework assignment
Assessment Rationale And Relationship

A substantial formal unseen examination is appropriate for the assessment of the material in this module. 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.

In the event of on-campus examinations not being possible, an on-line alternative assessment will be used for written examination 1.

Reading Lists

Timetable