Irreducible polynomial in Ring-LWE

Question

In Ring-LWE polynomials are chosen from the ring $R_q=\mathbb{Z}_q[x]/(x^n+1)$, where $n$ is a power of two.

As far as I understand, to create a ring the polynomial $x^n+1$ has to be irreducible (see the page 2, second paragraph, of this paper). But if we select $q=1\pmod{2n}$ (as done in many cases for efficient NTT multiplication), the field has $n$th roots of unity and the polynomial can be factored.

As an example let's take $q=17$ and $x^4+1$ can be factored in $(x+2)(x+8)(x+9)(x+15)$. Real implementations with $q=7681$ and $n=256$ can be factored similarly.

I can't understand where I am making a mistake. Thank you for your help.

Answer 1

The cited paper, as well as the theorem of R-LWE in that paper only requires $f$ to be irreducible over the rationals. For this requirement one usually uses $f = x^n+1$ with $n$ a power of $2$. This polynomial is reducible modulo $q$ but it is okay for the proof to go through.

The cited paper suggested to use cyclotomic polynomial $\phi_n = 1+x+x^2+...+x^{n-1}$ with $n$ prime. This polynomial is irreducible over $Z$. For some prime $q$, it is also irreducible over $Z_q$.

Ex: $n = 11$, $q=17$, $\phi_n = x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$ is irreducible mod $q$.