Algebraic Background
Definition : Cyclotomic Polynomial
A cyclotomic polynomial is a polynomial of the form $\Phi_m(x) = \prod_{1 \le k \le m, \gcd(k, m) = 1} (x – \zeta_m^k)$, where $\zeta_m$ is a primitive $m$-th root of unity. Cyclotomic polynomials are irreducible over the rationals and play a key role in defining cyclotomic number fields.
For example
For $m = 2^4$, there are $n = \varphi(m) = m/2 = 8$ primitive $m$-th roots of unity. So the cyclotomic polynomial $\Phi_{2^4}(x)$ has degree $n = 8$. If $\zeta_m$ is any primitive $m$-th root of unity, since its order is $m$, thus $\zeta_m^n = \sqrt{1} = -1$, which implies $\zeta_m^n + 1 = 0$. Therefore, the cyclotomic polynomial is uniquely determined as $$ > \Phi_{2^4}(x) = x^8 + 1. > $$
Definition : Cyclotomic Number Field
A cyclotomic number field is a number field of the form $K = \mathbb{Q}(\zeta_m)$, where $\zeta_m$ is a primitive $m$-th root of unity, i.e., $\zeta_m = e^{2 \pi i / m}$ is any root of cyclotomic polynomial $\Phi_m(x) = x^{m/2} + 1$.
Definition : Cyclotomic Ring
The ring of integers of $K$ is given by $\mathcal{O}_K = \mathbb{Z}[\zeta_m]$. As we know, $\mathbb{Z}[\zeta_m] \cong \mathbb{Z}[x]/\langle \Phi_m(x) \rangle$, where $\Phi_m(x)$ is the $m$-th cyclotomic polynomial. $\mathbb{Z}[\zeta_m]$ is a special ring known as the cyclotomic ring, which has rich algebraic properties. So, why choose the cyclotomic polynomial $\Phi_m(x)$ as the modulus, not any other irreducible polynomial?
It ensures that any principal ideal in the cyclotomic ring $\mathbb{Z}[x] / \langle \Phi_m(x) \rangle$ can be uniquely factored into prime ideals. This property is crucial for the security and efficiency of lattice-based cryptographic schemes, as it allows for a well-defined notion of ideal lattices and facilitates the reduction from the Ring-LWE problem to worst-case lattice problems.
For example
For $m = 2^2$, the cyclotomic number field is $K = \mathbb{Q}(\zeta_4)$, where $\zeta_4$ is a primitive $4$-th root of unity. The ring of integers of $K$ is $\mathcal{O}_K = \mathbb{Z}[\zeta_4]$, let $\zeta_4$ be the primitive $4$-th root of unity.Let’s see an example of factorization of a principal ideal in this ring : $$ > (4) = (2^2) = ((1 + \zeta_4)^2 \cdot (1 – \zeta_4)^2) = (1 + \zeta_4)^2 \cdot (1 – \zeta_4)^2 > $$ Both factors are irreducible, but they are also associated, $1 – \zeta_4 = (-\zeta_4) \cdot (1 + \zeta_4)$ where $-\zeta_4$ is a unit in ring $\mathbb{Z}[\zeta_4]$, then two principal ideals generated by them are equal, i.e., $(1 + \zeta_4) = (1 – \zeta_4)$. Therefore, the factorization of the principal ideal $(4)$ can be uniquely written as $$ > (4) = (1 + \zeta_4)^4 > $$ where prime ideal $(1 + \zeta_4)$ appears with multiplicity $4$ in the factorization of the principal ideal $(4)$.
Let’s see a counter-example where the modulus is not an cyclotomic polynomial. Consider a general ring $\mathbb{Z}[\sqrt{-3}] = \mathbb{Z}[x]/\langle x^2 + 3 \rangle$. In this ring, the principal ideal $(4)$ can be factored as $$ > (4) = (2)^2 = (1 + \sqrt{-3}) \cdot (1 – \sqrt{-3}) > $$ Here, all factors $(2), (1 + \sqrt{-3}), (1 – \sqrt{-3})$ are irreducible in $\mathbb{Z}[\sqrt{-3}]$, but unlike the cyclotomic case, they are not associated, and the factorization is not unique up to units, i.e., $(2) \ne (1 + \sqrt{-3}) \ne (1 – \sqrt{-3})$.