Chapter 1: Finite Fields and Polynomial Rings

01.What this chapter is for

By the end of this chapter you will be able to read the symbol

$$R_q \;=\; \mathbb{Z}_q[X] \,/\, (X^n + 1)$$

and compute inside it without help. That symbol packs four separate ideas on top of one another:

1. integers reduced modulo $q$,
2. polynomials in a variable $X$ whose coefficients are those reduced integers,
3. polynomial long division, and
4. a way of saying "any polynomial whose degree is at least $n$ should be reduced down using the rule $X^n = -1$."

The post-quantum cryptosystems standardised by NIST in 2024 (Kyber and Dilithium) live entirely inside $R_q$. Every key, every ciphertext, every signature is an element of $R_q$. Every operation in those schemes is addition or multiplication in $R_q$. So before any cryptography can make sense, you have to be comfortable adding, multiplying, and reducing inside this object.

02.Who this is written for

Someone in their first semester of college who has never seen abstract algebra. The presentation does not assume any prior exposure to groups, rings, fields, ideals, or quotient rings. Modular arithmetic ("clock arithmetic") is built up from scratch. Polynomials are introduced as a kind of book-keeping for a few numbers in a row, not as a formal object first.

The pedagogy throughout is the same. Whenever a new word appears, the first thing you see is a small numerical example you can check by hand. The precise definition follows once the example has done its work. You are never asked to take a definition on faith.

03.Reading order

The notes are meant to be read in order. Each one builds on the previous.

1. Sets and Notation. The vocabulary for collections of numbers. The symbols $\in$, $\subseteq$, $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$.
2. Operations and Closure. What it means to "add" or "multiply" inside a set, and why some sets are closed under an operation while others are not.
3. Groups, Rings, and Fields. Three escalating structures, each adding more guarantees than the last. Definitions arrive after worked examples.
4. Modular Arithmetic. Reducing integers modulo a small number. The clock face is the right picture. This is the engine that runs the rest of the chapter.
5. The Ring $\mathbb{Z}_n$. Modular arithmetic, repackaged as a ring. The first ring you will compute in.
6. Polynomials and the Polynomial Ring. Polynomials in a variable $X$. How to add and multiply them. Why their degree is a problem we have to solve.
7. Quotient Rings and Ideals. The trick that fixes the degree problem. The quotient construction, which the symbol "$/$" in $R_q$ is doing.
8. The Target Ring $R_q$. Putting all the pieces together. The ring $R_q$ at last, and the specific values of $n$ and $q$ that Kyber and Dilithium use.

04.A note on numbers

Every example in this chapter uses small numbers. Modular arithmetic with $n = 5$ before $n = 17$, $n = 17$ before any prime in the hundreds. Polynomials of length 4 before polynomials of length 256. The reasoning at the cryptographic sizes (where $n = 256$ and $q$ is in the millions) is identical in shape. The numbers are just bigger. Everything in this chapter can be checked on paper.

05.Where this leads

After this chapter, the natural next question is: why this particular ring and not a different one? That question is the subject of Chapter 2: Why Post-Quantum Cryptography?. Chapter 2 is a standalone story about cryptography, RSA, the quantum threat, and how the NIST competition arrived at lattice-based schemes. It does not introduce any new mathematics. It explains why the mathematics in this chapter is the right mathematics for the job.