Skip to content

MATH4260

Coding theory and cryptography

Linear, cyclic, BCH and evaluation codes, coding bounds, finite fields, information theory and noisy channels, classical and public-key cryptography, key agreement and authentication.

16 chapters · 32 sectionsEN · 繁 · 简
My course notes

Your progress

0/ 32 sections marked complete

Next section: Distance, linear codes and syndromes

Completion marks are saved in this browser.

This course in the web

In the MATH4260 notes

Theorem cards
82
Definitions
48
Counterexamples
34
Concept lenses
22
Histories of ideas
6
Proof X-rays
32

Sections with a history of an idea

None of these is on the timeline yet.

No concept lens from this course is recorded in the web yet.

Open this course in the knowledge map

Counts cover the 32 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.

In the webTheorem cards 82 · Definitions 48 · Counterexamples 34 · Concept lenses 22 · Histories of ideas 6 · Proof X-rays 32

None of these is on the timeline yet.

No concept lens from this course is recorded in the web yet.

Open this course in the knowledge map

Counts cover the 32 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.

Chapter 1 · 4 sections

Linear codes

Distance, error correction and syndromes over the binary field.

Theorems 14 · Definitions 8Counterexamples 4Lenses 4History 1Proof X-rays 5

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 1.1

    Distance, linear codes and syndromes

    Derive correction guarantees and syndrome decoding for binary linear codes.

  2. 1.2

    Extended Hamming codes and SECDED

    Derive the extended Hamming syndrome decoder, its single-error correction and double-error detection guarantee, and the limits outside that guarantee.

  3. 1.3

    Packing, covering and the limits of code size

    Prove finite and asymptotic Hamming, Gilbert–Varshamov and Plotkin bounds, separating existence, linearity and efficient construction.

  4. 1.4

    Weight enumerators and MacWilliams duality

    Derive the dual weight transform by additive-character orthogonality, obtain exact coefficient and moment constraints, and test candidate code distributions.

Chapter 2 · 2 sections

2. Cyclic codes

Consecutive roots and a finite syndrome decoder.

Theorems 4Counterexamples 2Lenses 2Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 2.1

    Consecutive roots and a cyclic decoder

    Prove a consecutive-root distance bound and decode a binary length-seven cyclic code.

  2. 2.2

    Cyclic codes as polynomial ideals

    Relate cyclic shifts to multiplication modulo x^n−1 and construct a binary cyclic code.

Chapter 3 · 4 sections

3. Information theory

Entropy and binary prefix codes for finite sources.

Theorems 13 · Definitions 11Counterexamples 6Lenses 1History 1Proof X-rays 4

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 3.1

    Entropy and binary prefix codes

    Derive the entropy lower bound and a finite-source prefix-code construction.

  2. 3.2

    Huffman coding and lossless block-source rates

    Prove the greedy prefix-code algorithm, its exact cost certificate and entropy bounds, then explain how independent blocks approach the source entropy.

  3. 3.3

    Noisy channels, mutual information and a decoding converse

    Measure the information retained by a finite channel and prove a necessary rate bound for reliable binary communication.

  4. 3.4

    The coding theorem for a finite memoryless channel

    Prove capacity achievability by information-density threshold decoding and a weak converse for arbitrary input correlations.

Chapter 4 · 4 sections

4. Public-key arithmetic

RSA correctness and the security limits of textbook arithmetic.

Theorems 9 · Definitions 5Counterexamples 3Lenses 3History 2Proof X-rays 4

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 4.1

    RSA: modular arithmetic and public-key encryption

    Prove RSA correctness on all residue classes and distinguish textbook arithmetic from secure encryption.

  2. 4.2

    ElGamal encryption and a conditional secrecy proof

    Prove correctness and chosen-plaintext security under decisional Diffie–Hellman, account for bounded fair-bit sampling, and exhibit malleability.

  3. 4.3

    RSA signatures and full-domain hashing

    Define chosen-message forgery, exhibit textbook RSA attacks, and prove a conditional full-domain-hash theorem in the random-oracle model.

  4. 4.4

    Schnorr identification and nonce reuse

    Prove the correctness, extraction and honest-verifier simulation of a discrete-log identification protocol, then examine its signature transformation and nonce failure.

Chapter 5 · 2 sections

5. Classical cryptography

Affine substitutions and precise information leakage.

Theorems 6 · Definitions 4Counterexamples 2Lenses 2History 1Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 5.1

    Classical cryptography: affine ciphers and the information they preserve

    Derive affine decryption, recover keys from observations, and distinguish exact leakage from statistical frequency analysis.

  2. 5.2

    Matrix ciphers, periodic keys and information leakage

    Analyze Hill and Vigenère ciphers using modular linear algebra, known plaintext and exact secrecy obstructions.

Chapter 6 · 1 section

6. Source compression

Construct optimal finite binary prefix codes.

Theorems 4 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 6.1

    Huffman coding and optimal prefix trees

    Prove the greedy construction minimizes expected prefix-code length for a finite source.

Chapter 7 · 1 section

7. Noisy channels

Study information and error correction for a binary symmetric channel.

Theorems 2 · Definitions 2Counterexamples 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 7.1

    A binary symmetric channel and repetition

    Compute one-use mutual information and examine a finite repetition code under an explicit noise model.

Chapter 8 · 1 section

8. Secret sharing

Prove threshold reconstruction and information-theoretic privacy.

Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 8.1

    Polynomial threshold secret sharing

    Prove reconstruction and perfect privacy for a finite-field threshold scheme.

Chapter 9 · 1 section

9. Polynomial evaluation codes

Study evaluation-code distance, errors and erasures.

Theorems 2 · Definitions 2Counterexamples 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 9.1

    Evaluation codes, errors and erasures

    Derive the distance and error-erasure guarantee of a polynomial evaluation code.

Chapter 10 · 2 sections

10. Key agreement

Study modular key agreement and its security assumptions.

Theorems 4 · Definitions 3Counterexamples 3Lenses 2Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 10.1

    Diffie–Hellman key agreement

    Derive modular key agreement and distinguish its arithmetic from authentication and security.

  2. 10.2

    Diffie–Hellman security experiments

    Compare passive security experiments, computational assumptions, and active substitution.

Chapter 11 · 1 section

11. Message authentication

Study a one-time authentication experiment and its limits.

Theorems 1 · Definitions 1Counterexamples 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 11.1

    A one-time authentication experiment

    Prove a substitution bound for a one-time affine tag and examine key reuse.

Chapter 12 · 1 section

12. Decoding limits

Relate finite-alphabet estimation error to conditional entropy.

Theorems 1Counterexamples 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 12.1

    Error probability and conditional entropy

    Prove a finite-alphabet Fano bound and interpret its limitations.

Chapter 13 · 1 section

13. Coding bounds

Compare greedy existence and Hamming packing bounds.

Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 13.1

    Greedy codes and Hamming bounds

    Construct a finite code greedily and compare existence and packing bounds.

Chapter 14 · 3 sections

Finite fields

Construction, structure and discrete logarithms in finite fields.

Theorems 9 · Definitions 5Counterexamples 3Lenses 3Proof X-rays 3

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 14.1

    Why finite fields exist and how their subfields fit together

    Construct finite fields from irreducible polynomials and prove prime-power size, cyclic units, Frobenius periods and subfield classification.

  2. 14.2

    Compute and construct finite fields with certified tests

    Implement polynomial-residue arithmetic, prove an irreducibility test, and give bounded-randomness field construction with an explicit failure probability.

  3. 14.3

    Element orders, roots of unity and discrete logarithms

    Construct roots of a specified order and prove baby-step giant-step and prime-power discrete-log algorithms with explicit cost assumptions.

Chapter 15 · 2 sections

BCH codes

Designed distance and syndrome decoding of BCH codes.

Theorems 4 · Definitions 4Counterexamples 2Lenses 2Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 15.1

    Consecutive roots and the BCH distance guarantee

    Construct cyclic codes from extension-field roots, prove the Vandermonde distance bound, and build a binary code of length fifteen.

  2. 15.2

    Locate two bit errors from BCH syndromes

    Derive a complete two-error decoder for the binary length-fifteen BCH code and distinguish guaranteed correction from behavior outside the error radius.

Chapter 16 · 2 sections

Evaluation codes

Reed-Solomon codes and Berlekamp-Welch decoding.

Theorems 5Counterexamples 2Lenses 2History 1Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 16.1

    Polynomial evaluation, interpolation and optimal distance

    Construct Reed–Solomon codes, prove their parameters and erasure recovery, and derive parity checks from interpolation.

  2. 16.2

    Unknown errors become a linear system

    Prove polynomial-time unique Reed–Solomon decoding with a monic error locator, including failure certificates and unused error budget.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details