MA7009 - Discrete Mathematical Structures (2024/25)
Module specification | Module approved to run in 2024/25 | ||||||||||||
Module title | Discrete Mathematical Structures | ||||||||||||
Module level | Masters (07) | ||||||||||||
Credit rating for module | 20 | ||||||||||||
School | School of Computing and Digital Media | ||||||||||||
Total study hours | 200 | ||||||||||||
|
|||||||||||||
Assessment components |
|
||||||||||||
Running in 2024/25(Please note that module timeslots are subject to change) |
|
Module summary
This module, together with MA7010, Number Theory for Cryptography provides the essential grounding needed to complement the algorithms and techniques encountered in spring semester modules in cryptography and information security. It aims to demonstrate the theoretical underpinning that delivers security, particularly of asymmetric public key algorithms while also allowing students to appreciate the limitations and potential vulnerabilities of systems encountered elsewhere in their course. It is designed to complement, in particular, MA7011 -Applications in Cryptography and Cryptanalysis and can be taken either before or after this module depending on a student’s start point without disadvantaging them.
Techniques in discrete mathematics that have application in cryptography will be explored in a thorough way with emphasis on getting students to a level where the mathematics of cryptography and the language used is accessible to them irrespective of their background and prior study.
Beginning with a brief review of topics normally encountered in undergraduate mathematics and computer science courses, new topics will then be introduced ab initio with an emphasis on supported learning via problem classes, worked examples and formative assessment.
Prior learning requirements
Programme entry requirements
Syllabus
Key concepts in discrete mathematics: quotients, remainders and the greatest common divisor. Algorithms for finding the gcd equation. Operations on sets, closure, commutativity, associativity, inverses and identities. Polynomials and the gcd of polynomials, irreducible polynomials. The integers modulo p and methods for finding inverses modulo p for a natural number n. Solutions of systems of linear congruence equations. Euler totient function, primitive elements and the Euler Fermat Theorem.
Rings and Fields: axioms and key properties; examples of finite and infinite fields and the construction of GF(pn) as a quotient ring whose elements are polynomials. Minimum polynomials, Fermat’s Little Theorem. Homomorphisms and isomorphisms in rings and fields, the Frobenius automorphism.
Elliptic curves: motivating definitions and geometric interpretations; elliptic curves over finite fields; tangents to elliptic curves and the addition and scalar multiplication of points on elliptic curves. The discrete logarithm problem for elliptic curves over finite fields. Applications of the discrete logarithm problem to cryptography.
Lattices: principles for construction, examples, specification of a lattice using a finite set of basis elements. The short vector problem and the closest vector problem for lattices specified with a long basis.
Combinatorics and probability: permutations and combinations, repeated elements in a set. Discrete probability distributions and applications (e.g. the birthday paradox and applications to collision algorithms).
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 which involve discussion of the ideas and an opportunity for students to practice the mathematical techniques. The remaining hours of private study will allow students to complete background reading, work on exercises and prepare for assessment.
Learning outcomes
This module aims to enable students to:
LO1: Describe, understand in detail and apply key concepts in discrete mathematics relevant to cryptography;
LO2: Implement algorithms and demonstrate an understanding of their complexity;
LO3: Understand and apply the properties of mathematical objects (e.g. elliptic curves, lattices) and how trapdoor functions can be used to deliver a public key cryptography system.
Bibliography
https://londonmet.rl.talis.com/modules/ma7009.html
Core Text:
Stanoyevitch, A. Introduction to Cryptography (independently published)
ISBN 979-8651423514
Recommended Texts:
Blake I, Seroussi, G and Smart, N. Elliptic Curves in Cryptography;
Cambridge University Press – ebook published 2013
Vermani, L.R and Vermani, S A Course in Discrete Mathematical Structures;
Imperial College Press 2012