Polynomial Ring Notation: R_q, X^n + 1, Roots of Unity and the NTT

Structured lattice schemes do their arithmetic with polynomials instead of long integer vectors. A polynomial of degree less than $n$ is stored as its $n$ coefficients, so every ring element is also a vector, and every ring operation is also a structured matrix operation. The tables below list the symbols, how to read them aloud, and the chapters where they appear. The variable is written $x$ in chapters 1.6 and 2.x and $X$ in 3.3, 3.5 and FIPS 203/204; both mean the same indeterminate.

Polynomial rings

Symbol	Read as	Meaning on this site	Example	Used in
$\mathbb{Z}[x]$	“Z adjoin x”	All polynomials in $x$ with integer coefficients.	$3 - x + 7x^2$	2.6, 2.4, 3.6, 1.6, 3.2
$\mathbb{Z}_q[X]$	“Z q of X”	Polynomials whose coefficients are integers modulo $q$ .	$16 + 5X \in \mathbb{Z}_{17}[X]$	3.5, 3.3, 2.3, 3.6
$\mathbb{Z}[x]/(x^n + 1)$	“Z x modulo x to the n plus one”	Quotient ring: polynomials of degree less than $n$ , where products are reduced using $x^n = -1$ . $n$ is a power of 2.	$x^3 \cdot x^2 = x^5 = -x$ for $n = 4$	2.4, 2.6, 3.6, 1.6, 2.5, 3.2
$R$	“R”	Shorthand for the integer ring of the chapter, usually $\mathbb{Z}[x]/(x^n+1)$ ; in 2.6 it can also be $\mathbb{Z}[x]/(x^n-1)$ .	$f, g \in R$	2.6, 2.4, 3.6, 3.2, 1.6
$R_q = R/qR$	“R q”	The same ring with every coefficient also reduced modulo $q$ : $\mathbb{Z}_q[x]/(x^n+1)$ . Its elements are what Kyber and Dilithium store.	$s \in R_q$	3.3, 2.3, 3.1, 2.6, 2.4, 2.5
$R_p = R/(p)$	“R p”	NTRU’s second, small modulus (typically $p = 3$ ). Written $R/(q)$ and $R/qR$ interchangeably.	$F_p = f^{-1} \pmod{p}$	2.6
$\mathbb{Z}[x]/(x^n - 1)$	“mod x to the n minus one”	Original NTRU ring: $x^n = +1$ , so products wrap around without a sign change (cyclic).	$x^5 = x$ for $n = 4$	2.6, 1.6, 5.1
$\mathbb{Z}[x]/(x^p - x - 1)$	“mod x to the p minus x minus one”	NTRU Prime’s ring, with $p$ prime; chosen to avoid the extra structure of cyclotomic rings.	$x^p = x + 1$	2.6

Which ring each scheme uses

Scheme	Ring	$n$	$q$	Chapter
ML-KEM (Kyber)	$\mathbb{Z}_q[X]/(X^{256}+1)$	256	3329	3.1, 3.5
ML-DSA (Dilithium)	$\mathbb{Z}_q[X]/(X^{256}+1)$	256	8,380,417	3.3
Falcon (FN-DSA)	$\mathbb{Z}[x]/(x^n+1)$ , mod $q$	512 or 1024	12289	3.6
Original NTRU	$\mathbb{Z}[x]/(x^n-1)$	scheme-dependent	power of 2 or prime, $q \gg p$	2.6
NTRU Prime	$\mathbb{Z}[x]/(x^p-x-1)$	$p$ prime	prime	2.6

Polynomials as vectors

A ring element $a = a_0 + a_1 X + \dots + a_{n-1} X^{n-1}$ is identified with its coefficient vector $(a_0, a_1, \dots, a_{n-1})$ . Addition is coordinate-wise. Multiplication is polynomial multiplication followed by reduction: in $X^n + 1$ rings every $X^{n+k}$ becomes $-X^k$ . That sign flip is why the product is called a negacyclic convolution.

Worked example in $\mathbb{Z}_{17}[X]/(X^4 + 1)$ with $a = 1 + 2X + 3X^3$ and $b = 2 + X^2$ . The schoolbook product is $2 + 4X + X^2 + 8X^3 + 3X^5$ . Replace $X^5 = X \cdot X^4 = -X$ :

ab = 2 + (4 - 3)X + X^2 + 8X^3 = 2 + X + X^2 + 8X^3 \pmod{17}.

The same product is a matrix–vector product. Column $j$ of the matrix below holds the coefficients of $X^j a$ : each column is the previous one shifted down by one, with the coefficient that falls off the bottom re-entering at the top with its sign flipped. Such a matrix is called anti-circulant (or negacyclic). In a $X^n - 1$ ring there is no sign flip and the matrix is an ordinary circulant, which is the “circulant block matrix” of the NTRU lattice in 1.6 and 2.6.

M_a = \begin{pmatrix} 1 & -3 & 0 & -2 \\ 2 & 1 & -3 & 0 \\ 0 & 2 & 1 & -3 \\ 3 & 0 & 2 & 1 \end{pmatrix}, \qquad M_a \begin{pmatrix} 2 \\ 0 \\ 1 \\ 0 \end{pmatrix} \equiv \begin{pmatrix} 2 \\ 1 \\ 1 \\ 8 \end{pmatrix} \pmod{17}.

This is the ring-versus-matrix view: a Ring-LWE sample $b = a s + e$ in $R_q$ is an ordinary LWE system $b = M_a s + e$ whose $n \times n$ matrix is determined by just $n$ numbers. The matrix is written with columns here; with the row convention used in the embedding guides, use its transpose.

Size of a polynomial

Symbol	Read as	Meaning on this site	Example	Used in
$\\|a\\|_\infty$	“infinity norm of a”	Largest absolute coefficient, with coefficients mod $q$ first taken in the centred range $(-q/2, q/2]$ . For a vector of polynomials, the maximum over all of them.	$\\|3 - 5X + X^2\\|_\infty = 5$	3.3, 2.5, 2.4, 2.6
$\\|a\\|$	“norm of a”	Euclidean length of the coefficient vector. Ring-SIS solutions and Falcon signatures are bounded this way.	$\\|1 + X - X^2\\| = \sqrt{3}$	2.4, 3.6
$\\|h\\|_1$	“one-norm of h”	Sum of absolute coefficients. In 3.3 it counts the 1-bits of Dilithium’s hint vector.	$\\|h\\|_1 > \omega$ means too many hint bits	3.3
small, ternary		A polynomial whose coefficients are tiny. Ternary means every coefficient is in $\{-1, 0, 1\}$ . These are the short vectors of ring lattices.	$f = 1 - X + X^3$	2.6, 2.4, 3.3

Roots of unity and the NTT

Fast multiplication in $R_q$ uses roots of unity modulo $q$ . The letters are not used consistently across the literature, and on this site $\zeta$ means a different root in each chapter that uses it. Always check which power of it equals $-1$ .

Symbol	Read as	Meaning on this site	Example	Used in
$\omega$	“omega”	In 3.5: a primitive $m$ -th root of unity in $\mathbb{Z}_q$ , meaning $\omega^m \equiv 1$ and no smaller positive power is 1. In 3.3 the same letter is Dilithium’s maximum hint weight.	$2^8 \equiv 1 \pmod{17}$ , so 2 is a primitive 8th root	3.5, 3.3
$\psi$	“psi”	A primitive $2n$ -th root of unity. The roots of $X^n + 1$ are its odd powers $\psi, \psi^3, \dots, \psi^{2n-1}$ .	$\psi = 2$ mod 17 for $n = 4$ : roots 2, 8, 15, 9	3.5
$\zeta$	“zeta”	The fixed root of a specific scheme. ML-KEM: $\zeta = 17$ , a primitive 256th root mod 3329 ( $17^{128} \equiv -1$ ). ML-DSA: $\zeta = 1753$ , a primitive 512th root mod 8,380,417 ( $\zeta^{256} \equiv -1$ ). In 3.2 and 1.6 it is a complex root, $\zeta = e^{i\pi/n}$ or $\zeta_{2n}$ .	$\zeta^{\mathrm{BitRev}_7(k)}$ twiddle factors	3.5, 3.3, 3.2, 1.6
$\gamma_i$	“gamma i”	In 3.5: the constants of ML-KEM’s 128 quadratic factors $X^2 - \gamma_i$ , with $\gamma_i = \zeta^{2\,\mathrm{BitRev}_7(i)+1}$ . Unrelated to the Hermite constant $\gamma_n$ .	$\gamma_0 = 17$	3.5
$\mathrm{ntt}(a),\ \mathrm{intt}(\hat a)$	“N T T of a”	The number-theoretic transform and its inverse: evaluate $a$ at the roots (or reduce it modulo the factors), then map back.	$\mathrm{intt}(\mathrm{ntt}(a)) = a$	3.5, 3.1, 3.3
$\hat a,\ \hat s,\ \hat f_i$	“a hat”	In 3.1 and 3.3: the NTT-domain representation of a polynomial. In 2.2 the hat means Babai’s output vector instead.	$\hat f_i = f(\zeta^{2i+1})$	3.1, 3.3
$\mathrm{BitRev}_7(k)$	“bit-reverse seven of k”	Write $k$ in 7 bits and reverse them. ML-KEM stores its twiddle factors in this order.	$\mathrm{BitRev}_7(1) = 64,\ \mathrm{BitRev}_7(3) = 96$	3.5
$\cong$	“is isomorphic to”	Two rings with the same structure. In 3.5 it is the Chinese-remainder splitting behind the NTT.	$R_q \cong \prod_{i=0}^{127} \mathbb{Z}_q[X]/(X^2 - \gamma_i)$	3.5

The algebraic view: number fields and ideals

For $n$ a power of 2, $X^n + 1$ is the $2n$ -th cyclotomic polynomial, so $\mathbb{Z}[x]/(x^n+1)$ is the ring of integers of a cyclotomic number field. Chapter 1.6 uses this language; the rest of the site mostly does not need it.

Symbol	Read as	Meaning on this site	Example	Used in
$\mathbb{Q}(\zeta_{2n})$	“Q adjoin zeta two n”	The cyclotomic field: rational combinations of powers of a primitive $2n$ -th complex root of unity. Its ring of integers is $\mathbb{Z}[\zeta_{2n}] \cong \mathbb{Z}[x]/(x^n+1)$ .	$\mathbb{Q}(i)$ for $n = 2$	1.6
$\sigma: R \to \mathbb{C}^n$	“sigma”	In 3.2: the canonical embedding, evaluating a polynomial at the complex roots $\zeta, \zeta^3, \dots, \zeta^{2n-1}$ . Everywhere else $\sigma$ is a Gaussian width.	$f \mapsto (f(\zeta), f(\zeta^3), \dots)$	3.2
ideal lattice		A lattice that is (the image of) an ideal of the ring, so it is closed under multiplication by $x$ . In an $x^n + 1$ ring that multiplication is a negacyclic rotation: shift the coefficients and negate the one that wraps.	$x \cdot (a_0, a_1, a_2, a_3) = (-a_3, a_0, a_1, a_2)$	1.6

Modules: vectors and matrices of polynomials

Module-LWE and Module-SIS replace the single ring element by short vectors and small matrices of ring elements. Superscripts give the shape, exactly as for $\mathbb{Z}_q^n$ .

Symbol	Read as	Meaning on this site	Example	Used in
$R_q^k$	“R q to the k”	Vectors of $k$ ring elements. Kyber’s rank $k = 2, 3, 4$ selects ML-KEM-512, -768, -1024.	$s \in R_q^k$	3.1, 2.3, 3.3
$R_q^{k \times \ell}$	“R q k by ell”	Matrices with $k$ rows and $\ell$ columns of ring elements. Dilithium uses $(k, \ell) = (4,4), (6,5), (8,7)$ .	$A \in R_q^{k \times \ell}$	3.3, 2.5, 2.3
$a^\top s$	“a transpose s”	Inner product of two module vectors: $\sum_i a_i s_i$ , each product taken in $R_q$ .	$b = a^\top s + e \in R_q$	2.3, 3.1
$R^m,\ R^{k+\ell}$	“R to the m”	Module vectors over the integer ring, used for Ring-SIS and Module-SIS solutions.	$(z_1, \ldots, z_m) \in R^m$	2.4

Each ring element is an $n$ -vector, so $A \in R_q^{k \times \ell}$ is an integer matrix of size $kn \times \ell n$ built from $k\ell$ anti-circulant blocks. For ML-KEM-768 that is a $768 \times 768$ matrix described by nine polynomials.

NTRU and Falcon symbols

Symbol	Read as	Meaning on this site	Example	Used in
$f, g$	“f, g”	The two small secret polynomials. $(f, g)$ is the short vector hidden in the NTRU lattice.	ternary, about $n/3$ nonzero coefficients	2.6, 1.6, 3.6
$f^{-1},\ F_q,\ F_p$	“f inverse”	The inverse of $f$ in $R_q$ (named $F_q$ in 2.6) or in $R_p$ ( $F_p$ ). Computed with the extended Euclidean algorithm.	$f \cdot F_q \equiv 1 \pmod q$	2.6, 3.6, 1.6
$h$	“h”	The public key. Chapters 1.6 and 3.6 use $h = g f^{-1} \bmod q$ ; the encryption chapter 2.6 uses $h = p \cdot F_q \cdot g$ , which puts the factor $p$ into the key instead of the message step.	$h \in R_q$	2.6, 1.6, 3.6
$F, G$	“capital F, G”	Falcon’s second pair of trapdoor polynomials, completing $(f, g)$ to a full short basis.	$fG - gF = q$	3.6
$\Lambda_h$	“lambda h”	The NTRU lattice of pairs $(u, v) \in R^2$ satisfying one linear congruence with $h$ , a $2n$ -dimensional lattice. 1.6 writes the condition as $v \equiv hu$ , 3.6 as $u + vh \equiv 0$ ; both are the same kind of lattice with the roles of the coordinates swapped.	$(f, g) \in \Lambda_h$ when $g \equiv hf$	1.6, 3.6

Scheme-specific functions

Symbol	Meaning	Used in
$\mathrm{HighBits}(r),\ \mathrm{LowBits}(r)$	Dilithium splits each coefficient as $r = r_1 \cdot 2\gamma_2 + r_0$ with $r_0$ centred; HighBits returns $r_1$ , LowBits returns $r_0$ . Applied coefficient-wise to polynomials and vectors.	3.3, 2.5
$h$ (Dilithium), $\omega$	The hint vector that lets the verifier recompute HighBits, and $\omega$ , the maximum number of 1s it may contain. Not the NTRU public key.	3.3
Compress, Decompress	Kyber’s lossy rounding of coefficients to $d$ bits (12 to 10 bits for $u$ , 12 to 4 for $v$ in 3.1). FIPS 203 defines $\mathrm{Compress}_d(x) = \lceil (2^d/q)\,x \rfloor \bmod 2^d$ and $\mathrm{Decompress}_d(y) = \lceil (q/2^d)\,y \rfloor$ . Chapter 3.1 describes them in words.	3.1

Same symbol, different meaning

Symbol	Ring meaning	Other meaning on this site
$\zeta$	Primitive 256th root mod 3329 (3.5); primitive 512th root mod 8,380,417 (3.3)	Complex root of unity $e^{i\pi/n}$ (3.2, 1.6)
$\omega$	Primitive root of unity (3.5)	Maximum hint weight in Dilithium (3.3)
$\gamma_i$	NTT base-case constants (3.5)	Hermite constant $\gamma_n$ (1.3, 1.4); Dilithium bounds $\gamma_1, \gamma_2$ (3.3)
$\sigma$	Canonical embedding (3.2)	Gaussian standard deviation (2.3, 6.3 and others)
$h$	NTRU / Falcon public key (1.6, 2.6, 3.6)	Dilithium hint (3.3); hash value in 6.4
$\hat{\ }$	NTT-domain value (3.1, 3.3)	Babai’s output $\hat v$ (2.2)
$\Phi$	Would be a cyclotomic polynomial in the literature	On this site only the LLL potential function (1.5)
$\mathcal{O}$	Would be a ring of integers in the literature	On this site only big-O notation (4.x)
$\mathcal{K}$	Would be a number field in the literature	On this site a convex body (1.3)

Conventions we follow

Ring elements are polynomials of degree less than $n$ , identified with their coefficient vectors $(a_0, \dots, a_{n-1})$ , lowest degree first.
Coefficients mod $q$ are taken in the centred range $(-q/2, q/2]$ whenever a size or norm is measured.
$x$ and $X$ denote the same indeterminate; chapters that follow FIPS 203/204 use $X$ .
Module shapes use superscripts: $R_q^k$ for vectors, $R_q^{k \times \ell}$ for matrices, as with $\mathbb{Z}_q^{m \times n}$ .
Multiplication matrices are written with columns $X^j a$ . In the row convention of chapters 7.x and g6k-rs, transpose them.

8.4 Rings and polynomials