Notation

August 25, 20267 min readbeginner

Every symbol used in the book, with the note that introduces it. Ordered roughly as the book meets them.

01.Sets and numbers

Symbol	Meaning	Introduced in
$\in$	is an element of	Sets and Notation
$\subseteq$	is a subset of	Sets and Notation
$\{x : P(x)\}$	the set of $x$ satisfying $P$	Sets and Notation
$\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$	naturals, integers, rationals, reals	Sets and Notation
$\lvert A \rvert$	the number of elements of a finite set	Sets and Notation

Symbol	Meaning	Introduced in
$a \bmod n$	the remainder in $\{0, \ldots, n-1\}$	Modular Arithmetic
$a \equiv b \pmod n$	$a$ and $b$ are in the same residue class	Modular Arithmetic
$\operatorname{mod}$	the operator itself, named rather than applied	Modular Arithmetic
$\mathbb{Z}_n$	the integers modulo $n$ , as a ring	The Ring $\mathbb{Z}_n$
$\mathbb{F}_q$	the finite field with $q$ elements, $q$ prime here	The Ring $\mathbb{Z}_n$
$\mathbb{F}_q^{\times}$	the non-zero elements under multiplication	Roots of Unity in a Finite Field
$a^{-1}$	the multiplicative inverse of $a$	The Ring $\mathbb{Z}_n$

Symbol	Meaning	Introduced in
$\mathbb{Z}_q[X]$	polynomials in $X$ with coefficients in $\mathbb{Z}_q$	Polynomials and the Polynomial Ring
$\deg a$	the degree of a polynomial	Polynomials and the Polynomial Ring
$R_q$	$\mathbb{Z}_q[X]/(X^n+1)$ , the ring everything lives in	The Target Ring $R_q$
$X^n = -1$	the negacyclic reduction rule defining $R_q$	Quotient Rings and Ideals
$n$	the ring degree, $256$ in both standards	The Target Ring $R_q$
$q$	the modulus: $3329$ for ML-KEM, $8380417$ for ML-DSA	The Target Ring $R_q$

Symbol	Meaning	Introduced in
$\mathcal{L}(B)$	the lattice generated by the columns of $B$	What a Lattice Is
$\lVert v \rVert$	Euclidean norm	Short Vectors: SVP and CVP
$\lVert v \rVert_\infty$	infinity norm, the largest coefficient in absolute value	Rejection Sampling, or Fiat-Shamir With Aborts
$\det \mathcal{L}$	lattice determinant, the volume per lattice point	Measuring a Lattice: Determinant and Minkowski's Theorem
$\lambda_1$	the length of the shortest non-zero vector	Exercises
$U$	a unimodular matrix, $\det U = \pm 1$	Good and Bad Bases
$\gamma$	approximation factor in $\gamma$ -SVP	Short Vectors: SVP and CVP

Symbol	Meaning	Introduced in
$\langle a, s \rangle$	inner product, multiply componentwise and add	Noise Breaks Linear Algebra
$\chi$	the error distribution	The Learning With Errors Problem
$\leftarrow$	is drawn at random from	The Learning With Errors Problem
$\text{CBD}_\eta$	centred binomial distribution with parameter $\eta$	Where the Noise Comes From
$\eta$	the centred binomial width	Where the Noise Comes From
$k$	module rank, how many polynomials in the secret	Module-LWE
$\ell$	the second module rank, ML-DSA only	The Parameter Sets

Symbol	Meaning	Introduced in
$\zeta$	a primitive $2n$ th root of unity	Roots of Unity in a Finite Field
$\hat{a}$	$a$ in the transformed domain	The Negacyclic NTT
$\odot$	pointwise multiplication	The Negacyclic NTT
$t$	a twiddle factor inside a butterfly	The Butterfly and Bit Reversal
$\operatorname{circ}_-(a)$	the negacyclic circulant of $a$	Ring-LWE

Symbol	Meaning	Introduced in
$A$	the public matrix, $k \times k$	Key Generation
$\rho$	the 32-byte seed that regenerates $A$	Key Generation
$\mathbf{s}, \mathbf{e}$	secret and error vectors	Key Generation
$\mathbf{t}$	the public value $A\mathbf{s} + \mathbf{e}$	Key Generation
$\mathbf{r}, \mathbf{e}_1, e_2$	the encryptor's ephemeral secret and errors	Encryption
$\mathbf{u}, v$	the two ciphertext components	Encryption
$\text{Encode}(m)$	a message bit as $0$ or $\lceil q/2 \rceil$	Encryption
$\delta, \delta'$	the decryption error, without and with compression	Why Decryption Works
$d_u, d_v$	compression widths in bits	Compression and Ciphertext Size
$z$	the implicit-rejection seed	The Fujisaki-Okamoto Wrapper

Symbol	Meaning	Introduced in
$\mathbf{s}_1, \mathbf{s}_2$	the signing secret and its error	Key Generation
$\mathbf{t}_1, \mathbf{t}_0$	the public and retained halves of $\mathbf{t}$	Key Generation
$d$	the truncation width, $13$	Key Generation
$\mathbf{y}$	the ephemeral commitment randomness	Signing
$\mathbf{w}, \mathbf{w}_1$	the commitment and its high bits	Signing
$c$	the challenge, $\tau$ coefficients of $\pm 1$	Signing
$\tau$	the challenge weight	The Parameter Sets
$\mathbf{z}$	the response $\mathbf{y} + c\mathbf{s}_1$	Signing
$\mathbf{h}$	the hint vector	Signing
$\gamma_1$	the range of $\mathbf{y}$	The Parameter Sets
$\gamma_2$	the bucket width for high and low bits	The Parameter Sets
$\beta$	the bound $\tau\eta$ on $c\mathbf{s}_1$	The Parameter Sets
$\omega$	the cap on hint weight	The Parameter Sets

Symbol	Meaning	Introduced in
$m$	the Barrett constant $\lfloor 2^k/q \rfloor$	Barrett Reduction
$R$	the Montgomery radix, a power of two	Montgomery Reduction
$\tilde{x}$	$x$ in Montgomery form, $xR \bmod q$	Montgomery Reduction
$q'$	the Montgomery constant, $qq' \equiv -1 \pmod R$	Montgomery Reduction
$r, c$	sponge rate and capacity, summing to 1600	The Sponge Construction
$\theta, \rho, \pi, \chi, \iota$	the five Keccak round steps	Inside Keccak-f[1600]
$\oplus, \wedge, \lnot$	XOR, AND, NOT	Inside Keccak-f[1600]

Some letters are reused across chapters with different meanings, which is unavoidable because the source standards use them that way.

$\rho$ is a 32-byte seed in ML-KEM and ML-DSA key generation, and separately the name of Keccak's rotation step. They are unrelated.

$c$ is the challenge polynomial in ML-DSA and the sponge capacity in Keccak. Also the ciphertext in ML-KEM.

$r$ is the sponge rate, and also the encryption randomness in ML-KEM's wrapper.

$m$ is the Barrett constant and also the message.

Context disambiguates all of them, and no note uses two senses at once.

FeedbackBook mode