Exercises

Several notes in this chapter end with small checks of their own. These are the chapter-wide set, drawing on all nine notes.

01.1. Closure

For each of $\{0,1,2,3,4\}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\{a/b : b \text{ odd}\}$, decide closure under $+$, $-$, $\cdot$, and division by non-zero elements.

Answer.

$\{0,1,2,3,4\}$ as ordinary integers is closed under none of them. $3 + 4 = 7$ escapes, $1 - 3 = -2$ escapes, $2 \cdot 3 = 6$ escapes, $1/2$ escapes. (Under arithmetic modulo 5 it is closed under all four, which is the point The Ring $\mathbb{Z}_n$ makes.)

$\mathbb{Z}$ is closed under $+$, $-$ and $\cdot$, but not division: $1/2 \notin \mathbb{Z}$.

$\mathbb{Q}$ is closed under all four, which is what makes it a field.

$\{a/b : b \text{ odd}\}$ is closed under all of $+$, $-$ and $\cdot$, since sums and products of such fractions keep an odd denominator. Division fails: $1 \div 2 = 1/2$ has an even denominator. So this is a ring but not a field, and a useful reminder that "contains fractions" and "is a field" are different claims.

02.2. Clock arithmetic

Compute $25 + 11 \pmod{12}$ and $-37 \bmod 12$, and verify $-37 \equiv 11 \pmod{12}$.

Answer. $25 + 11 = 36 = 3 \times 12$, so $36 \equiv 0 \pmod{12}$.

For $-37$: the representative in $\{0, \ldots, 11\}$ is found by adding multiples of 12 until non-negative. $-37 + 48 = 11$, so $-37 \bmod 12 = 11$.

Checking the congruence: $11 - (-37) = 48 = 4 \times 12$, a multiple of 12, so $-37 \equiv 11 \pmod{12}$.

The sign convention matters and is a common source of bugs. Many programming languages return $-1$ for -37 % 12, not $11$. The mathematician's $\operatorname{mod}$ always lands in $\{0, \ldots, n-1\}$, which is the convention Modular Arithmetic uses throughout.

03.3. A field and a non-field

Find $3^{-1}$ in $\mathbb{Z}_7$. Then show $\mathbb{Z}_{15}$ is not a field.

Answer. In $\mathbb{Z}_7$, try multiples of 3: $3, 6, 2, 5, 1$. The fifth gives $3 \times 5 = 15 \equiv 1$, so $3^{-1} = 5$.

For $\mathbb{Z}_{15}$, take the element $3$. Its multiples are $3, 6, 9, 12, 0, 3, 6, \ldots$, cycling through five values and never reaching $1$. So $3$ has no inverse and $\mathbb{Z}_{15}$ is not a field.

The reason is the criterion from The Ring $\mathbb{Z}_n$: $15 = 3 \times 5$ is composite, and any element sharing a factor with the modulus is a zero divisor rather than a unit. Here $3 \times 5 = 15 \equiv 0$, so $3$ and $5$ multiply to zero without either being zero.

04.4. Extended Euclid

Find integers $x, y$ with $3x + 17y = 1$, and conclude $3^{-1} \bmod 17$.

Answer. Run the Euclidean algorithm on $17$ and $3$:

$$17 = 5 \times 3 + 2, \qquad 3 = 1 \times 2 + 1, \qquad 2 = 2 \times 1 + 0 .$$

Back-substitute from the remainder $1$:

$$1 = 3 - 1 \times 2 = 3 - (17 - 5 \times 3) = 6 \times 3 - 1 \times 17 .$$

So $x = 6$ and $y = -1$.

Reducing modulo 17, $6 \times 3 = 18 \equiv 1$, so $3^{-1} \equiv 6 \pmod{17}$.

This is the general method behind the trial-and-error of exercise 3, and it is what an implementation uses. It also computes the Montgomery constant $q'$ in Chapter 7.

05.5. Polynomial multiplication modulo 7

Compute $(1 + 2X + 3X^2)(4 + 5X)$ in $\mathbb{Z}_7[X]$.

Answer. Multiply first over the integers, pairing every term with every term:

$$4 + 13X + 22X^2 + 15X^3 .$$

Then reduce each coefficient modulo 7: $4$, $13 \equiv 6$, $22 \equiv 1$, $15 \equiv 1$. So

$$(1 + 2X + 3X^2)(4 + 5X) \;=\; 4 + 6X + X^2 + X^3 \quad \text{in } \mathbb{Z}_7[X].$$

Note there is no reduction in the exponent here. $\mathbb{Z}_7[X]$ allows arbitrary degree, and only the coefficients live modulo 7. Cutting the degree down is the separate step that Quotient Rings and Ideals introduces.

06.6. Polynomial long division

Divide $X^4 + X^2 + 1$ by $X^2 + X + 1$ over $\mathbb{Z}$.

Answer. The quotient is $X^2 - X + 1$ and the remainder is $0$.

Check by multiplying back:

$$(X^2 + X + 1)(X^2 - X + 1) \;=\; X^4 + X^2 + 1 .$$

So the division is exact, and $\deg r < \deg f$ holds trivially since $r = 0$. This is the factorisation that makes $X^4 + X^2 + 1$ reducible, which matters when choosing a modulus polynomial: a reducible one would make the quotient ring have zero divisors.

07.7. Negacyclic reduction in general

In $R_q$ for any $q$ and $n$, compute $X \cdot X^{n-1}$ and then $X^{n+2}$.

Answer. $X \cdot X^{n-1} = X^n$, and the defining rule of $R_q$ is $X^n = -1$. So the product is $-1$, a constant.

That is worth pausing on. Two polynomials of positive degree multiplied to give a constant, which cannot happen in $\mathbb{Z}[X]$. The quotient construction is what makes it possible.

For $X^{n+2}$: write it as $X^n \cdot X^2 = (-1)X^2 = -X^2$.

The general rule is that any exponent $n + k$ folds down to $-X^k$, and exponents beyond $2n$ fold twice and come back positive.

8. A full product in $\mathcal{R}_{17}$

Compute $(1+X)(1 + X + X^2 + X^3)$ in $\mathcal{R}_{17}$ with $n = 4$.

Answer. Schoolbook first:

$$(1+X)(1 + X + X^2 + X^3) \;=\; 1 + 2X + 2X^2 + 2X^3 + X^4 .$$

Then reduce with $X^4 = -1$, so the $X^4$ term becomes $-1$ and lands on the constant:

$$(1 - 1) + 2X + 2X^2 + 2X^3 \;=\; 2X + 2X^2 + 2X^3 .$$

All coefficients are already in $\{0, \ldots, 16\}$, so the modular step changes nothing.

The constant coefficient vanishing is the negacyclic flip doing exactly what it does in ML-KEM's toy example, where the same mechanism turned $3 + 2X^4$ into $1$.

09.9. Checking an ML-KEM parameter, and a correction

Verify that $q = 3329$ is prime, and check whether $3329 \equiv 1 \pmod{512}$.

Answer. $3329$ is prime. Trial division by every prime up to $\sqrt{3329} \approx 57.7$ finds no factor.

The second claim is false, and the exercise is worth doing precisely because of that.

$$3329 \;=\; 6 \times 512 + 257, \qquad \text{so} \qquad 3329 \;\equiv\; 257 \pmod{512}.$$

The manuscript this chapter was migrated from asserted $3329 \equiv 1 \pmod{512}$ and asked the reader to confirm it. It cannot be confirmed, because it is not true, and the falsehood is not incidental. The condition $q \equiv 1 \pmod{2n}$ with $n = 256$ is exactly the requirement for a length-256 negacyclic transform, and ML-KEM famously does not satisfy it. That is the $q = 3329$ quirk in Chapter 4, the reason the transform runs seven levels instead of eight.

What is true is the weaker statement

$$3329 \equiv 1 \pmod{256}, \qquad \text{since } 3328 = 13 \times 256 ,$$

which is what gives ML-KEM its primitive $256$th root of unity and its incomplete transform.

So the corrected exercise is: verify that $3329$ is prime, that $256$ divides $3328$, and that $512$ does not. All three are checkable in a minute, and together they explain a design decision that echoes through the rest of the book.