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.


1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.