MA7010 - Number Theory for Cryptography (2025/26)
| Module specification | Module approved to run in 2025/26 | ||||||||||||
| Module title | Number Theory for Cryptography | ||||||||||||
| Module level | Masters (07) | ||||||||||||
| Credit rating for module | 20 | ||||||||||||
| School | School of Computing and Digital Media | ||||||||||||
| Total study hours | 200 | ||||||||||||
|
|||||||||||||
| Assessment components |
|
||||||||||||
| Running in 2025/26(Please note that module timeslots are subject to change) |
|
Module summary
This module, together with MA7009, Discrete Mathematical Structures provides the essential grounding you will need to complement the algorithms and techniques encountered in spring semester modules in cryptography and information security. It aims to describe relevant topics in the theory of the natural numbers that underpin much of 21st century cryptographic security. It is designed to complement, in particular, MA7011 - Applications in Cryptography and Cryptanalysis; you can take that either before or after this module depending on your start point without disadvantage.
Additionally, this module will support a series of mini investigations designed to develop your ability to take the ideas you encounter, apply them with realistic datasets and draw appropriate conclusions. These will principally be delivered via procedures written in the mathematical programming language MAPLE or the Python programming language in which you will be supported as you gain fluency.
The module will principally introduce you to topics in number theory but their application to cryptography will be stressed as they are introduced and in the initial weeks the module will also provide a brief overview of the subject of cryptography and its historical context.
Prior learning requirements
NA
Syllabus
Fundamental skills in mathematical programming through MAPLE and/or Python. (LO1)
Introduction/Recap of key terms and concepts in cryptography: symmetric and asymmetric cryptography. (LO3, LO4)
Introduction to number theory: early history, prime numbers and their distribution. The infinity of primes and the prime number theorem. Properties and distribution of primes. (LO2, LO3)
Prime testing: Fermat’s Little Theorem; probabilistic methods, Miller Rabin Test and other Monte Carlo methods. Carmichael numbers and Korselt’s criterion. The Agrawal-Kayal-Saxena primality test. (LO3, LO4)
Discrete logarithms and methods for their calculation (e.g. baby step-giant step, Pohlig-Hellman algorithms, Pollard Rho method). (LO2)
Congruence equations: applications of the Chinese Remainder Theorem to cryptography, quadratic residues and their properties. Gauss’ quadratic reciprocity theorem and techniques for solving congruence problems. Legendre and Jacobi symbols and their use in primality testing. (LO2, LO4)
Introduction to integer factorisation: methods covered will be selected from basic sieving algorithms, Fermat factorisation, Pollard’s rho method. (LO2, LO3)
Advanced methods for integer factorisation: quadratic sieve and number field sieve algorithms, factorisation using elliptic curves. Continued fractions and their use in integer factorisation. (LO4)
Complexity: polynomial and exponential time for algorithms; NP complete problems. (LO4)
Balance of independent study and scheduled teaching activity
The module has 200 learning hours. 4 hours per week contact is divided approximately equally between lectures covering background, theory and examples and workshops in PC Labs which involve discussion of the ideas and an opportunity for you to practice the mathematical techniques and to develop proficiency in programming via Maple and Python and investigating realistic data sets. The remaining hours of private study will allow you to follow a self-study python guide such as that at https://edube.org/study/pe1 that consolidates your knowledge of programming and the delivery of LO1, complete background reading, work on exercises and prepare for assessment.
Learning outcomes
This module aims to enable students to:
LO1: Acquire and consolidate skills in programming languages needed to support cryptographic investigation and to engage in self-reflection to identify and address any other areas of skills deficiency that may affect performance on the course.
LO2: Implement and evaluate asymmetric cryptographic algorithms, such as RSA and Elliptic Curve, and analyse their limitations and risks.
LO3: Explain how key theorems and algorithms encountered in the module can be used to demonstrate cryptographic security.
LO4: Demonstrate how the concepts in number theory encountered in the module find application in the modern technological world.