## F11PE1 Pure Maths E

Lecturer Dr Mark V Lawson

Lectures Tuesday 3.15, Wednesday 10.15 and Friday 9.15 all in CMG01

Tutorials 'C' students: Friday 10.15 in CMG01 (start week 2)

Tutorials 'E' students: Wednesday 1.15 in EM101 (start week 2)

Specimen exam papers and their solutions paper C and paper E and solutions

### E solutions

Summary

This course deals with the different ways in which data has to be encoded in order to be handled effectively. Three main topics will be discussed: cryptographic or secret codes; error-correction codes used, for example, in CD's and in transmitting data through space; and data compression codes used in reducing the amount of space needed to store data. The course uses algebraic ideas that you have encountered in previous years such as matrices and determinants, polynomials, and modular arithmetic.

Useful references

Norman L. Biggs,  Codes: an introduction to information, communication and cryptography, Springer, 2008.

L. N. Childs,  A concrete introduction to higher algebra, Springer, 2009.

Nigel Smart's website contains many useful resources.

Course contents
1. Introduction.
2. Cryptography.
3. Error correcting codes.
4. Huffman codes.
'C' students: Parts 1, 2 and 3.
'E' students: Parts 1,2, 3 and 4.

Syllabus.

Prerequisites

The prerequisites for this module are basic but essential: you must be able to handle matrices with confidence, particularly matrix multiplication and computing small determinants; you must also know about linear dependence and independence; you must know the basics of modular arithmetic; you must know the basics of polynomials; and you must know the basics of sets. Most of these prerequisites were covered in my first year module Algebra A. The remaining prerequisites should be second nature to anyone who has progressed through the first and third years.

Lectures
Syllabuses C and E

Cryptography

 1 2 3 4 5 6 7 Lecture 1 Introduction Lecture 4 Complexity theory Lecture 7 Prime numbers Lecture 10 The group U_{n} Lecture 13 The theorems of Fermat, Wilson and Euler's Lecture 16 Pollard rho heuristic OMITTED IN 2010 Lecture 19 One-time pad crypto generalities Lecture 2 Codes Lecture 5 Euclid's algorithm Lecture 8 Factorizing numbers Lecture 11 The Euler phi function Lecture 14 Primitive element theorem Lecture 17 Crypto Caesar and Vigenere ciphers Lecture 20 DES and AES Lecture 3 Algorithms Lecture 6 Lame's theorem Lecture 9 Group theory Lecture 12 Chinese remainder theorem Lecture 15 Testing for primes OMITTED IN 2010 Lecture 18 Hill ciphers affine block ciphers Lecture 21 Diffie-Hellman RSA

Error correcting codes

 8 and 9 Lecture 1: motivation Lecture 2: key definitions Lecture 3: encoding and decoding  with linear codes Lecture 4: Hamming codes and beyond

Huffman codes
Syllabus E only
Refer to Biggs Chapters 2 and 3 for details

 Codes The Kraft-McMillan number Sources and entropy Huffman codes Notes You can omit the proof of Theorem 2.13 but make sure you understand what this theorem is saying. For us entropy will always be to base 2. You can omit the proof of Theorem 3.12 but make sure you understand what this theorem is saying. Theorems whose proofs you must know: Theorem 2.5, Theorem 2.9.

Exercises and solutions

 Exercises 1 Exercises 2 Exercises 3 Exercises 4 Exercises 5 OMITTED IN 2010 Exercises 6 Homework Exercises 7 Solutions 1 Lectures 1,2 Solutions 2 Lectures 3,4 Solutions 3 part 1 Solutions 3 part 2 Lectures 5--8 Solutions 4 Lectures 9--14 Solutions 5 Lectures 15,16 Solutions 6 Lectures 18--21 Solutions 7 Lectures 22--30

18.X.2010