# RLWE Explanation

In RLWE, we often choose the following polynomial ring, where q is a prime, and n is a power of 2, e.g. $$2^k$$ $$\mathbb Z_q[X]/(X^n + 1)$$

We know that $${X^{2^k}} + 1$$ is an irreducible polynomial under $$Z$$, because of Cyclotomic Polynomial, but in this question, Considering $$\mathbb Z_{17}[X]/(X^4 + 1)$$ $$(X^4 + 1)$$ can be factorized into $$\mathbb (X^2 + 4)(X^2 - 4) = X^4 - 16 = X^4 + 1$$ because of $$Z_{17}$$, moreover it can even be factorized into $$(x + 15)(x + 9)(x + 8)(x + 2)$$ under $$Z_{17}$$

Then why would we need to choose an irreducible polynomial like $${X^{2^k}} + 1$$ at the first place when it is reducible under $$Z_q$$, moreover what are the advantages of choosing $${X^{2^k}} + 1$$ as our ideal, and does choosing a large enough prime q(much larger than 17) prevents the above scenario from happening?

Thanks!

• have a look here in this article web.eecs.umich.edu/~cpeikert/pubs/ideal-lwe.pdf May 19, 2022 at 18:13
• for the second question they choose $X^{2^k}+1$ because it useful to use FFT and hence improving efficiency May 19, 2022 at 18:16
• Thanks! It makes perfect sense for the second question, and I'll work on the article for the first question, Thanks again! May 19, 2022 at 18:36

And choosing $$q$$ such that the cyclotomic polynomial does not split completely is useless, because the hardness of the RLWE problem only depends on the bit length of $$q$$, not on its format.
By the way, when we implement BGV, FV, CKKS or other schemes based on the RLWE, we often restrict our choices of $$q$$ to force $$X^n + 1$$ to split completely, so that we can use RNS (aka double-CRT) representation.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 17, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}