Chapter 2: Mathematical preliminaries

The algebra-heavy parts of post-quantum cryptography in this book repeatedly use four kinds of algebraic object: integers modulo $n$, finite fields, polynomial quotient rings, and vectors or matrices over those rings. Lattice schemes (Part II), code-based schemes (Part IV), and the post-quantum zero-knowledge layer (Part VI) all reach into this toolbox. Hash-based signatures (Part III) do not. They are built on hash functions and Merkle trees, and Chapter 14 introduces the small set of primitives they need on its own terms. Chapter 2 defines each algebraic object, states the one or two theorems the later chapters cite, and implements the basic operations in Python. Readers who want to verify they have the assumed background should see Prerequisites.

Every code block in this chapter is self-contained and runnable in isolation: the chapter’s block verifier runs each block in a fresh Python namespace, so every block that depends on an earlier helper restates that helper at the top. A reader copying a single block into a file gets a script that runs without any external imports. The trailing # ==> marker is the expected-output assertion checked by tools/verify_code_blocks.py. There is no error handling on any helper. A helper given bad input crashes loudly, which is the intended behavior for a toy implementation. Asserts are used as narration of preconditions, not as error recovery.

A calculation that reappears

One kind of calculation dominates what later chapters do with integers: raise a base to a large power and reduce the result modulo another integer. Here is the smallest instance that shows up. Take the prime 13 and the base 7, and compute $7^{200} \bmod 13$.

Python’s built-in pow does this in time logarithmic in the exponent by repeated squaring:

direct = pow(7, 200, 13)
print(direct)
# ==> 3

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch02/, one file per block. Appendix C covers the clone and the environment they run on.

Fermat’s little theorem gives a shortcut (Shoup, 2009). For any prime $p$ and any integer $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod{p}$. For $p = 13$ and $a = 7$, that means $7^{12} \equiv 1 \pmod{13}$. Since $200 = 16 \cdot 12 + 8$, the exponent $200$ collapses modulo 12 to 8, so $7^{200} \equiv 7^{8} \pmod{13}$:

by_fermat = pow(7, 8, 13)
print(by_fermat)
# ==> 3

Both routes return the same element of $\mathbb{Z}/13\mathbb{Z}$, because they are computing the same thing by different paths. Everything in the rest of the chapter is machinery for doing this kind of calculation carefully in richer algebraic settings. Integers modulo $n$ are the first setting. Finite fields, polynomial quotient rings, and matrices over those rings are the rest of the catalog.

Integers modulo n

Fix a positive integer $n$. Two integers $a$ and $b$ are congruent modulo $n$, written $a \equiv b \pmod{n}$, when $n$ divides $a - b$. The set of equivalence classes under congruence is $\mathbb{Z}/n\mathbb{Z}$, the integers modulo $n$. Addition and multiplication pass to equivalence classes without modification, so $\mathbb{Z}/n\mathbb{Z}$ is a commutative ring with identity (Shoup, 2009).

An element $a$ of $\mathbb{Z}/n\mathbb{Z}$ is a unit (has a multiplicative inverse) exactly when $\gcd(a, n) = 1$. The extended Euclidean algorithm computes $\gcd(a, n)$ together with integers $x$ and $y$ satisfying $a x + n y = \gcd(a, n)$. When $\gcd(a, n) = 1$, the coefficient $x$ reduced modulo $n$ is the inverse of $a$ (Shoup, 2009). The code below implements this.

Two theorems about powers come up in the number-theoretic chapters. Fermat’s little theorem says that for a prime $p$ and an integer $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod{p}$ (Shoup, 2009). Euler’s generalization says that for $n \geq 2$ and any $a$ with $\gcd(a, n) = 1$, $a^{\varphi(n)} \equiv 1 \pmod{n}$ (Shoup, 2009). The function $\varphi(n)$ is the number of integers $a$ with $1 \leq a \leq n$ and $\gcd(a, n) = 1$. For a prime $p$ the count $\varphi(p)$ equals $p - 1$, and Euler collapses to Fermat.

The Chinese remainder theorem handles multiple moduli at once. Suppose $n_1, n_2, \ldots, n_k$ are pairwise coprime, and let $n$ be their product. The map $\mathbb{Z}/n\mathbb{Z} \to (\mathbb{Z}/n_1\mathbb{Z}) \times \cdots \times (\mathbb{Z}/n_k\mathbb{Z})$ that sends $a$ to the tuple $(a \bmod n_1, \ldots, a \bmod n_k)$ is a ring isomorphism (Shoup, 2009). Concretely, arithmetic in $\mathbb{Z}/n\mathbb{Z}$ becomes arithmetic in each factor $\mathbb{Z}/n_i\mathbb{Z}$ in parallel, and the reverse map reassembles a result in $\mathbb{Z}/n\mathbb{Z}$ from its images in the factors.

Fast exponentiation (repeated squaring) computes $a^k \bmod n$ in $O(\log k)$ modular multiplications by walking the binary representation of the exponent from low bit to high bit (Shoup, 2009). Chapter 4 uses it to build toy RSA, and Chapter 9 uses it to raise a primitive root of unity to the powers the number theoretic transform needs.

Modular exponentiation

Raise a base to a non-negative exponent modulo $n$ by repeated squaring. The loop walks the exponent from low bit to high bit, squaring the running base each step and multiplying it into the result whenever the current bit is 1.

def mod_pow(base, exponent, modulus):
    assert exponent >= 0, "exponent must be non-negative"
    assert modulus >= 1, "modulus must be at least 1"
    result = 1 % modulus
    base = base % modulus
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

# 7^200 mod 13, matching the opening calculation.
print(mod_pow(7, 200, 13))
# ==> 3

Python’s built-in pow(base, exponent, modulus) does the same computation with a more careful C implementation, and the later chapters use it wherever speed matters. The explicit version here exists to show what the built-in is doing inside.

The extended Euclidean algorithm

Given non-negative integers $a$ and $b$, find their greatest common divisor $g$ together with coefficients $x$ and $y$ satisfying $a x + b y = g$. When $b = 0$ the gcd is $a$ and the trivial coefficients $(1, 0)$ work; otherwise, solve recursively on $(b, a \bmod b)$ and repackage the coefficients by the usual substitution. Non-negativity is a real precondition, not a formality: on a negative argument the recursion can bottom out on a negative value and hand back a negative $g$. mod_inv is unaffected, because it reduces its argument modulo $n$ before calling.

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def mod_inv(a, modulus):
    assert modulus > 1, "modulus must be greater than 1"
    g, x, _ = ext_gcd(a % modulus, modulus)
    assert g == 1, "inverse does not exist: a and modulus share a factor"
    return x % modulus

# Compute 17^-1 modulo 43 and verify the inverse.
inverse = mod_inv(17, 43)
product = (17 * inverse) % 43
print(inverse)
print(product)
# ==> 38
# ==> 1

The assert is narration, not error handling. It marks a precondition for the toy reader. A production implementation would raise a specific exception, but a toy helper that quietly returns garbage on invalid input teaches the wrong lesson.

Finite fields

When $n$ is a prime $p$, every nonzero element of $\mathbb{Z}/p\mathbb{Z}$ has a multiplicative inverse, so $\mathbb{Z}/p\mathbb{Z}$ is a field. Write it $\mathbb{F}_p$ when treating it as a field, and $\mathbb{F}_p^*$ for the set of its nonzero elements under multiplication.

$\mathbb{F}_p^*$ is a cyclic group of order $p - 1$ (Lidl & Niederreiter, 1997). Cyclic means there is an element $g$ with the property that every nonzero element of $\mathbb{F}_p$ equals $g^i$ for some integer $i$ in $\{0, 1, \ldots, p - 2\}$. Such a $g$ is called a primitive element or a generator of $\mathbb{F}_p^*$. For the concrete primes this book uses, a generator is found by trial, as Exercise 2 walks through for $p = 17$.

Artin’s conjecture, and what is known without it

Artin’s conjecture predicts that a fixed integer $g$ is a primitive root for a positive density of primes, and so for infinitely many. It applies to any $g$ that is neither $-1$ nor a perfect square, which includes $g = 2$. Both exclusions are forced: $-1$ has order 2, and a perfect square is a quadratic residue, so its order divides $(p - 1)/2$. Hooley proved the conjecture under the Generalized Riemann Hypothesis (Hooley, 1967). Unconditionally, the situation is much weaker. Gupta and Murty proved that a set of thirteen numbers built from three primes must contain one that is a primitive root modulo infinitely many primes (Gupta & Murty, 1984). Heath-Brown sharpened the count from thirteen to three: at least one of $2$, $3$, or $5$ works. The proof does not identify which one (Heath-Brown, 1986). No single explicit base, including $g = 2$, is currently known unconditionally to be a primitive root for infinitely many primes (Fan & Pollack, 2025; Moree, 2012).

The prime fields $\mathbb{F}_p$ are the only finite fields Part II builds from scratch. Chapter 11’s partial number theoretic transform computes inside quadratic extensions of $\mathbb{Z}_q$, which that chapter introduces where it needs them. Finite fields of the form $\mathbb{F}_{2^m}$ also exist and appear in the Classic McEliece treatment in Chapter 20. They are constructed as $\mathbb{F}_2[x] / (f(x))$ for an irreducible polynomial $f$ of degree $m$, which is an instance of the polynomial-quotient construction in the next subsection (Lidl & Niederreiter, 1997). Chapter 20 writes this field $\mathrm{GF}(2^m)$, where $m$ is the extension degree and the field has $2^m$ elements. The Goppa-code dimension parameter $k$ is a separate quantity and lives at the code level, not at the field level.

Polynomial rings and quotient rings

Fix a prime $p$. The polynomial ring $\mathbb{F}_p[x]$ is the set of polynomials in one variable with coefficients in $\mathbb{F}_p$, under the usual addition and multiplication of polynomials. $\mathbb{F}_p[x]$ is a Euclidean domain: for any $f, g$ in $\mathbb{F}_p[x]$ with $g$ nonzero there exist unique $q, r$ in $\mathbb{F}_p[x]$ with $\deg(r) < \deg(g)$ and $f = q g + r$ (Lang, 2002; Shoup, 2009). The zero polynomial has degree $-\infty$ by convention, which is what lets a zero remainder satisfy that bound. Finding $q$ and $r$ is polynomial long division, which the code below implements.

When $q$ is prime, the symbols $\mathbb{Z}_q$, $\mathbb{Z}/q\mathbb{Z}$, and $\mathbb{F}_q$ all refer to the same field. The book follows the convention used in NIST’s lattice specifications and writes $\mathbb{Z}_q$ when the modulus is the integer $q$ used by a scheme parameter set, and $\mathbb{F}_p$ when the prime $p$ is generic.

Given a polynomial $f$ in $\mathbb{F}_p[x]$ of degree $k$, the quotient ring $\mathbb{F}_p[x] / (f(x))$ consists of equivalence classes of polynomials modulo $f$. A canonical representative of each class is the polynomial of degree strictly less than $k$ obtained by taking the remainder on long division by $f$. Addition and multiplication in the quotient are performed in $\mathbb{F}_p[x]$ and then reduced modulo $f$ (Lang, 2002).

When $f$ is irreducible over $\mathbb{F}_p$, every nonzero element of $\mathbb{F}_p[x] / (f(x))$ has a multiplicative inverse, and the quotient is a field with $p^k$ elements (Lidl & Niederreiter, 1997). This is how the finite fields $\mathbb{F}_{p^k}$ are built. When $f$ is nonconstant and reducible, the quotient is still a commutative ring with identity, but it is not a field and it has zero divisors. It is still usable for arithmetic.

The lattice-based schemes in Part II work in quotient rings of the form $\mathbb{Z}_q[x] / (x^n + 1)$, where $q$ is a prime and $n$ is a power of two. With $n$ a power of two, $x^n + 1$ is the cyclotomic polynomial $\Phi_{2n}(x)$, and the quotient is the negacyclic ring of polynomials of degree less than $n$ in which $x^n$ is identified with $-1$. The parameter $q$ is then chosen so that multiplication in this ring admits an efficient number theoretic transform.

ML-KEM uses $q = 3329$ and $n = 256$ (National Institute of Standards and Technology, 2024). The prime 3329 satisfies $q - 1 = 2^8 \cdot 13$. So $\mathbb{Z}_q$ contains a primitive $256$-th root of unity but not a primitive $512$-th root. The polynomial $x^{256} + 1$ factors over $\mathbb{Z}_q$ into 128 degree-two irreducible polynomials rather than 256 linear factors (FIPS 203 §4.3, equation 4.10) (National Institute of Standards and Technology, 2024). Chapter 9 derives the condition behind this partial split, and Chapter 11 builds the corresponding transform.

For Chapter 2 it is enough to know that $\mathbb{F}_p[x] / (f(x))$ is a ring, that its elements are polynomials of bounded degree, and that multiplication is ordinary polynomial multiplication followed by reduction modulo $f$. Figure 2.1 shows that reduction in the negacyclic case at $n = 4$.

Figure 2.1. Reduction modulo $x^4 + 1$. The product of two degree-3 polynomials occupies seven coefficient slots. The three slots past degree 3 fold back onto degrees 0, 1, and 2 with their signs flipped, which is what makes the ring negacyclic.

Polynomials over a finite field

Represent a polynomial as a list of coefficients in ascending order, so the list [2, 1, 3] stands for $2 + x + 3 x^2$. Multiplication is the textbook $O(n^2)$ double loop. The result has degree at most $\deg(f) + \deg(g)$, and every entry is reduced modulo $p$ as it is accumulated. Chapter 9 replaces this with the number theoretic transform for the specific rings ML-KEM uses, but the naive version here is what the rest of Part II’s exposition assumes the reader has in mind.

def poly_mul(f, g, p):
    result = [0] * (len(f) + len(g) - 1)
    for i, a in enumerate(f):
        for j, b in enumerate(g):
            result[i + j] = (result[i + j] + a * b) % p
    return result

# Multiply (2 + x) by (3 + x^2) in F_5[x].
f = [2, 1]
g = [3, 0, 1]
print(poly_mul(f, g, 5))
# ==> [1, 3, 2, 1]

The constant term is $2 \cdot 3 \equiv 1 \pmod{5}$. The $x$ coefficient is $2 \cdot 0 + 1 \cdot 3 = 3$. The $x^2$ coefficient is $2 \cdot 1 + 1 \cdot 0 = 2$. The $x^3$ coefficient is $1 \cdot 1 = 1$. Reading the list back as a polynomial gives $1 + 3 x + 2 x^2 + x^3$ in $\mathbb{F}_5[x]$.

Polynomial reduction

Long division of a polynomial $a$ by a monic polynomial $f$ over $\mathbb{F}_p$ produces a remainder $r$ with $\deg(r) < \deg(f)$. Repeatedly peel off the top coefficient of $a$, subtract the appropriate multiple of $f$ from the tail, and drop the now-zero top coefficient. This helper assumes $f$ is monic for simplicity; a production helper would handle a general leading coefficient by dividing it out first. The first line reduces every incoming coefficient modulo $p$, so a caller that passes unreduced integers gets coefficients back in $\{0, \ldots, p-1\}$. That is not the same as a canonical representative, because the trailing zero coefficients are still left in place.

def poly_mul(f, g, p):
    result = [0] * (len(f) + len(g) - 1)
    for i, a in enumerate(f):
        for j, b in enumerate(g):
            result[i + j] = (result[i + j] + a * b) % p
    return result

def poly_mod(a, f, p):
    assert f[-1] == 1, "poly_mod requires f to be monic"
    a = [c % p for c in a]
    deg_f = len(f) - 1
    while len(a) - 1 >= deg_f:
        lead = a[-1]
        if lead != 0:
            for i in range(deg_f + 1):
                a[-1 - i] = (a[-1 - i] - lead * f[deg_f - i]) % p
        a.pop()
    return a

# In F_7[x], reduce (1 + x + x^3) * (2 + x^2) modulo x^3 + x + 1.
# Any multiple of the modulus reduces to the zero polynomial.
f_mod = [1, 1, 0, 1]
g = [2, 0, 1]
product = poly_mul(f_mod, g, 7)
print(poly_mod(product, f_mod, 7))
# ==> [0, 0, 0]

The modulus is a factor of the product by construction, so the remainder is the zero polynomial. poly_mod does not trim trailing zero coefficients, so the zero polynomial comes back as [0, 0, 0] rather than the shorter [0] or []. A caller that wants the shortest representation has to trim the result itself.

Vectors, matrices, and bases

A vector in $\mathbb{F}_p^n$ is an ordered tuple of $n$ elements from $\mathbb{F}_p$. An $m$-by-$n$ matrix over $\mathbb{F}_p$ is a rectangular array of elements of $\mathbb{F}_p$ with $m$ rows and $n$ columns. Addition is componentwise; scalar multiplication scales every entry by a fixed element of $\mathbb{F}_p$; matrix multiplication is the usual row-times-column rule. These operations make $\mathbb{F}_p^n$ a vector space over $\mathbb{F}_p$ (Dummit & Foote, 2004).

Two ideas from linear algebra carry into the later chapters. The first is rank. The rank of a matrix $A$ is the dimension of its row space. Equivalently, it is the dimension of its column space. The two dimensions are equal, even though the row and column spaces live in different ambient vector spaces when $A$ is rectangular. Gaussian elimination by row operations reduces $A$ to reduced row echelon form without changing its rank. The rank is the number of nonzero rows in the reduced form (Dummit & Foote, 2004). The code below implements this algorithm.

The second is a basis. A basis of $\mathbb{F}_p^n$ is a set of $n$ vectors that spans $\mathbb{F}_p^n$ and is linearly independent. Over a field, every spanning set contains a basis and every linearly independent set extends to a basis (Dummit & Foote, 2004). Over $\mathbb{Z}$, which is not a field, the word “basis” has a narrower meaning tied to the structure of integer lattices. Chapter 7 develops that narrower meaning in full; for this chapter, “basis over $\mathbb{F}_p$” is the only version in scope.

The standard dot product over $\mathbb{F}_p$ defines a symmetric bilinear form, which coding theory routinely calls an inner product, and it is used algorithmically (for example, in the syndrome calculation of a linear code). It is not positive definite: finite fields carry no compatible ordering, and a nonzero vector can be orthogonal to itself. Over $\mathbb{F}_2$, the nonzero vector $(1, 1)$ has self-inner-product $1 \cdot 1 + 1 \cdot 1 = 0$. What does carry over is the part coding theory needs. Orthogonality and orthogonal complements remain well defined, which is what a parity-check matrix relies on. Chapter 19 returns to this form over $\mathbb{F}_2$ when setting up linear codes.

Gaussian elimination over a finite field

Reduce a matrix over $\mathbb{F}_p$ to reduced row echelon form by processing one column at a time. The rank of the matrix is the number of pivots the algorithm places. Over a field this is straightforward because every nonzero scalar is invertible. Over a ring that is not a field, the algorithm breaks in informative ways. The lattice and code-based chapters each return to row reduction in a more delicate form. Inside the pivot-normalization step this block uses pow(a, p - 2, p) as the modular inverse, because the modulus is a prime and Fermat’s little theorem gives the inverse in one line. This is equivalent to the extended-Euclidean mod_inv from the earlier block. The Fermat form is just shorter when the modulus is known to be prime.

def gauss_eliminate(matrix, p):
    assert p > 1, "p must be prime; this helper does not test primality"
    m = [row[:] for row in matrix]
    rows = len(m)
    cols = len(m[0]) if m else 0
    rank = 0
    for col in range(cols):
        pivot = None
        for r in range(rank, rows):
            if m[r][col] % p != 0:
                pivot = r
                break
        if pivot is None:
            continue
        m[rank], m[pivot] = m[pivot], m[rank]
        # Fermat: for prime p, the inverse of a nonzero element is a^(p-2).
        inv = pow(m[rank][col], p - 2, p)
        m[rank] = [(x * inv) % p for x in m[rank]]
        for r in range(rows):
            if r != rank and m[r][col] % p != 0:
                factor = m[r][col]
                m[r] = [(m[r][c] - factor * m[rank][c]) % p for c in range(cols)]
        rank += 1
    return m, rank

matrix = [
    [1, 2, 3],
    [0, 1, 4],
    [2, 0, 0],
]
reduced, rank = gauss_eliminate(matrix, 5)
for row in reduced:
    print(row)
print("rank =", rank)
# ==> [1, 0, 0]
# ==> [0, 1, 4]
# ==> [0, 0, 0]
# ==> rank = 2

The third row of the input is twice the first row plus the second row, all in $\mathbb{F}_5$: $2 \cdot [1, 2, 3] + [0, 1, 4] = [2, 5, 10] \equiv [2, 0, 0] \pmod{5}$. So the three rows span a two-dimensional subspace, the algorithm correctly reports rank 2, and the third row reduces to zero.

When to reach for which tool

Each of the four algebraic objects in this chapter has a home in a later part of the book.

Object	Setting for	Chapters
Integers modulo $n$	Classical RSA and classical Diffie-Hellman	Chapter 4 (toy RSA) and Chapter 5 (toy Diffie-Hellman), both of them the foil for the post-quantum chapters that follow
Finite fields and polynomial quotient rings	The lattice-based schemes: the ring $\mathbb{Z}_q[x] / (x^n + 1)$ that ML-KEM works in, where the number theoretic transform gives a fast multiplication algorithm	Chapter 9
Matrices over $\mathbb{F}_2$	The code-based schemes: linear codes as subspaces of $\mathbb{F}_2^n$, binary Goppa codes over the extension field $\mathbb{F}_{2^m}$ in Classic McEliece, and HQC, whose security rests on quasi-cyclic syndrome decoding, a structured variant of the same decoding problem	Chapter 19 (linear codes), Chapter 20 (Classic McEliece), Chapter 21 (HQC)
Linear algebra over $\mathbb{Z}$	The lattice chapters: lattices as the integer combinations of a basis of $\mathbb{R}^n$, then basis reduction	Chapter 7 (building lattices), Chapter 13 (basis reduction)

Hash-based signatures in Part III sit outside this map entirely: they need hash functions and Merkle trees, not rings or matrices.

Where Chapter 2 ends and Chapter 3 picks up

This chapter answered “what is the object and how do I compute in it”. It said nothing about why anyone would build a cryptosystem on one. Chapter 3 asks the other question: given these objects, which computational problems over them are believed to be hard, and hard for a quantum adversary in particular.

The map from this chapter to that one is partial. Two of Chapter 3’s four families rest directly on the algebra above: short and close vectors in lattices, and syndrome decoding of a random linear code. A third rests on isogeny and endomorphism-ring problems over supersingular elliptic curves, which are not built from anything defined here. Chapter 3 defines the vocabulary it needs on the spot and leaves the full structure to Chapter 22. The fourth needs none of this chapter’s algebra at all, resting instead on the preimage and collision properties of hash functions.

Exercises

1. Use the chapter’s mod_pow helper to compute $7^{200} \bmod 13$. Verify the answer by computing $7^{8} \bmod 13$ (Fermat’s little theorem says $7^{12} \equiv 1 \pmod{13}$, and $200 = 16 \cdot 12 + 8$, so the exponent reduces to 8 modulo 12). Confirm the two answers agree and state what the common answer is.

2. Find a generator of $\mathbb{F}_{17}^*$. Try $g = 2$ first: compute $2^1, 2^2, \ldots, 2^{16}$ modulo 17 and check whether the sequence hits every nonzero element of $\mathbb{F}_{17}$ exactly once. If $g = 2$ does not work, try $g = 3$, then $g = 5$, and so on. Write out the full power sequence for the first generator you find.

3. Write a Python function that returns every root a polynomial in $\mathbb{F}_p[x]$ has in $\mathbb{F}_p$, by evaluating it at every element of $\mathbb{F}_p$ in turn. Apply the function to $f(x) = x^3 + x + 1$ over $\mathbb{F}_7$. List the values $f(0), f(1), \ldots, f(6)$ modulo 7. A polynomial of degree 2 or 3 over a field is irreducible if and only if it has no root in the field. (Any proper factorization of such a polynomial would include a linear factor, and linear factors correspond to roots.) State whether $f$ is irreducible and justify the answer from the values. The equivalence does not extend to degree 4 and higher: $(x^2 + 1)^2$ over $\mathbb{F}_3$ is reducible but has no root in $\mathbb{F}_3$.

4. Apply the chapter’s gauss_eliminate helper to the 4-by-4 matrix

   [[1, 2, 3, 4],
    [2, 3, 4, 5],
    [3, 4, 5, 6],
    [4, 5, 6, 7]]

   over $\mathbb{F}_7$. State the rank of the matrix and write one sentence explaining why the rank is what it is, in terms of a linear dependence among the rows of the original matrix. Hint: the rows form an arithmetic progression.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 2. A separate track, for rebuilding rather than reading: the package exercises/ch02-algebra has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch02 to grade your version against the suite that proves the reference one.

References

Dummit, D. S., & Foote, R. M. (2004). Abstract Algebra (3rd ed.). Wiley. https://www.wiley.com/en-us/Abstract+Algebra%252C+3rd+Edition-p-9780471433347

Fan, K. (Steve), & Pollack, P. (2025). Counting primes with a given primitive root, uniformly. Mathematika, 71(4), e70055. https://doi.org/10.1112/mtk.70055

Gupta, R., & Murty, M. R. (1984). A remark on Artin’s conjecture. Inventiones Mathematicae, 78, 127–130. https://doi.org/10.1007/BF01388719

Heath-Brown, D. R. (1986). Artin’s conjecture for primitive roots. Quarterly Journal of Mathematics, 37(1), 27–38. https://doi.org/10.1093/qmath/37.1.27

Hooley, C. (1967). On Artin’s conjecture. Journal Für Die Reine Und Angewandte Mathematik, 225, 209–220. https://doi.org/10.1515/crll.1967.225.209

Lang, S. (2002). Algebra (Revised 3rd, Vol. 211). Springer. https://link.springer.com/book/10.1007/978-1-4613-0041-0

Lidl, R., & Niederreiter, H. (1997). Finite Fields (2nd ed., Vol. 20). Cambridge University Press. https://www.cambridge.org/core/books/finite-fields/75BDAA74ABAE713196E718392B9E5E72

Moree, P. (2012). Artin’s primitive root conjecture: a survey. Integers, 12(6), 1305–1416. https://doi.org/10.1515/integers-2012-0043

National Institute of Standards and Technology. (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

Shoup, V. (2009). A Computational Introduction to Number Theory and Algebra (2nd ed.). Cambridge University Press. https://doi.org/10.1017/cbo9780511814549