Using ring R=$\mathbb{Z}[X]/(X^n+1)$

733 Views Asked by At

Currently studying Ring-LWE,here, and having trouble grasping a concrete definition of what this means, as a ring. My understanding is that everything in this ring is an integer polynomial, and that it must be reduced $X^n+1$, is this correct? Essentially working modulo $X^n+1$.

It then goes on to work in quotient group $R_q=R/qR$. When in this quotient group, would all elements have already been reduced $X^n+1$ and finally then reduced mod $q$?

2

There are 2 best solutions below

4
On BEST ANSWER

The polynomials are just multiplied as usual but any term $X^N$ is replaced by $-1$, $X^{n+1} \equiv -X$ etc. , as we consider $X^n+1$ to be equivalent to $0$.

All coefficients of those polynomials lie in $\mathbb{Z}_q$, so whenever they go above $q$, reduce them.

So a simple example: $n=3$, $q=3$, then $$(1+X+X^2)(1+2X+2X^2)= 1 + 2X + 2X^2 + X + 2X^2 + 2X^3 + X^2 + 2X^3 + 2X^4=1 + 3X + 5X^2 +4X^3 + 2X^4 \equiv 1+ 2X^2 + 4(-1) + 2(-X) \equiv (1-4) - 2X +2X^2 \equiv X +2X^2$$

for example (modulo calculation errors, working from screen)

1
On

Yes, working in $\Bbb Z[X]/(X^n+1)$ means working with integer polynomials modulo $X^n+1$.

As for the second question, yes, $R/qR$ means reducing first modulo $X^n+1$, then modulo $q$. However, by the third isomorphism theorem, this is essentially the same as first reducing modulo $q$, then reducing modulo $X^n+1$. Assuming $q$ is an integer, that way is usually easier to work with.