MATH3411 2023T3 Exam Information: Examinable Content
The final MATH3411 exam is worth 60 marks and you will have 4 hours to complete it.
The past exams (available on Moodle and via UNSW Library) give a good indication of the
questions and content that you might be asked by in this year’s exam.
You can omit the following sections from the course notes IN TOTAL:
ˆ 1.4 Morse Code
ˆ 2.15.1 Coset decoding
ˆ 4.10 Shannon’s Noisy Channel Coding Theorem
ˆ 4.11 Entropy of natural language (however, you need to know that R = 1.5 for English)
ˆ 5.7.3 Pollard’s ρ method (1975)
ˆ 5.7.4 Quadratic sieve method
ˆ 5.7.5 Shore’s Algorithm
ˆ 5.8 Random Number Generation
ˆ 6.4 The general case (binary)
ˆ 6.5 Cyclic codes
ˆ 6.6 The Golay codes
ˆ 6.7 Where next?
ˆ 7.2.3 Encryption Standards
ˆ 7.4.2 Massey-Omura protocol
ˆ 7.5.2 El Gamal public-key cryptography
ˆ 7.5.3 McEliece Encryption
ˆ 7.6 Digital signatures
ˆ 7.7 Probabilistic Encryption
ˆ 7.8 Recent Developments
1
You will NOT be tested on:
ˆ Section 4.8, Note 2, the Fano bound (H(A|B) ≤ H(pe) + pe log(u− 1))
ˆ Any additional material that was mentioned in lectures but is not in the Lecture Notes.
Otherwise, you should know all the definitions, results, and methods covered in lectures.
You should know the statements AND proofs or derivations of:
ˆ Theorem 2.1, p. 11 — ISBN error capability
ˆ Theorem 2.2, p. 31 — Sphere-packing condition/Sphere-packing bound.
ˆ Theorem 2.3, p. 33 — Minimum distance for linear codes.
ˆ Theorem 3.1, p. 47 — Kraft-McMillan Theorem
ˆ Theorem 3.2, pp. 51-52 — Minimal UD code conditions
ˆ Theorem 3.3, p. 54 — Huffman code theorem
ˆ Proposition 3.4, p. 55 — Huffman Code length (Knuth’s shortcut)
ˆ Section 4.1, p. 73 — Gibbs’ Inequality
ˆ Theorem 4.1, p. 73 — Maximum Entropy Theorem
ˆ Theorem 4.2, p. 74 — First Source-Coding Theorem
ˆ Section 4.4, pp. 75-77 — Shannon-Fano code length bounds
ˆ Section 4.9, pp. 89-91 — Capacity of Binary Symmetric Channel
ˆ Section 7.1.6, pp. 143-145 — Kasiski’s Method: how to calculate the index of coincidence Ic.
ˆ Section 7.5.1, pp. 151-153 — How/why RSA works
2
You should know the statements ONLY of:
ˆ Theorem 2.4, p. 37 — Standard form matrices
ˆ Theorem 4.3, p. 78 — Entropy of extensions: H(Sn) = nH(S)
ˆ Theorem 4.4, p. 79 — Shannon’s Source Coding Theorem
ˆ Theorem 4.5, p. 81 — Markov Entropy Theorem
ˆ Section 4.8, pp. 82-88 — Results relating H(A,B), H(A), H(A|B), I(A,B) etc.
ˆ Chapter 5 up to and including Subsection 5.7.2 — Number theory, algebra, primality
testing, factoring
ˆ Section 7.9.2, pp. 163-164 — Unicity distance
You should also understand and be able to solve all relevant tutorial problems, particularly those
related to the material listed above and those with YouTube solutions. The questions which are
not important to the course are marked “Skip!” – and you are welcome to do so.
In the MATH3411 exam, you will need to understand the principles of polyalphabetic substi-
tution ciphers and how frequency analysis and the structure of the underlying language can be
used to break them. You should also be aware of the problems and weaknesses of classical (pre-
1970) cryptosystems and how more recent advances in public-key cryptography address these
problems, as well as how public-key cryptography is used in practice and what its drawbacks
are.
For any BCH code question, you will be given the field to work in.