Skip to main content

Module

MAS3707 : Number Theory and Cryptography

  • Offered for Year: 2020/21
  • Module Leader(s): Dr Stuart Hall
  • Lecturer: Dr Oli King
  • Owning School: Mathematics, Statistics and Physics
  • Teaching Location: Newcastle City Campus
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, not all of which will be proved.
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

Please note that module leaders are reviewing the module teaching and assessment methods for Semester 2 modules, in light of the Covid-19 restrictions. There may also be a few further changes to Semester 1 modules. Final information will be available by the end of August 2020 in for Semester 1 modules and the end of October 2020 for Semester 2 modules.

Teaching Activities
Category Activity Number Length Student Hours Comment
Scheduled Learning And Teaching ActivitiesLecture91:009:00Present in Person
Scheduled Learning And Teaching ActivitiesLecture91:009:00Synchronous On Line Material
Structured Guided LearningLecture materials361:0036:00Non Synchronous Activities
Guided Independent StudyAssessment preparation and completion301:0030:00Completion of in course assessments
Structured Guided LearningStructured non-synchronous discussion181:0018:00Non Synchronous Discussion
Scheduled Learning And Teaching ActivitiesDrop-in/surgery41:004:00Office hour or discussion board activity
Guided Independent StudyIndependent study941:0094:00Lecture preparation, background reading, coursework review
Total200:00
Jointly Taught With
Code Title
MAS8707Number Theory & Cryptography
Teaching Rationale And Relationship

Non-synchronous online materials are used for the delivery of theory and explanation of methods, illustrated with examples, and for giving general feedback on assessed work. Present-in-person and synchronous online sessions are used to help develop the students’ abilities at applying the theory to solving problems and to identify and resolve specific queries raised by students, and to allow students to receive individual feedback on marked work. Students who cannot attend a present-in-person session will be provided with an alternative activity allowing them to access the learning outcomes of that session. In addition, office hours/discussion board activity will provide an opportunity for more direct contact between individual students and the lecturer: a typical student might spend a total of one or two hours over the course of the module, either individually or as part of a group.
Alternatives will be offered to students unable to be present-in-person due to the prevailing C-19 circumstances.
Student’s should consult their individual timetable for up-to-date delivery information.

Assessment Methods

Please note that module leaders are reviewing the module teaching and assessment methods for Semester 2 modules, in light of the Covid-19 restrictions. There may also be a few further changes to Semester 1 modules. Final information will be available by the end of August 2020 in for Semester 1 modules and the end of October 2020 for Semester 2 modules.

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

Exams
Description Length Semester When Set Percentage Comment
Written Examination1202A8024 hour take home paper
Other Assessment
Description Semester When Set Percentage Comment
Written exercise1M10Written exercises
Written exercise2M10Written exercises
Assessment Rationale And Relationship

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

Reading Lists

Timetable