C solutions

2010 syllabus E exam paper

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.

Leitfaden for crypto.

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.

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

8 and 9

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

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 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

---