I recently encountered the notation which is referred to as ring (in the description of a cryptography scheme, Dilithium, here, page 4):
[...] The key generation algorithm generates a $k \times l$ matrix $\bf{A}$ each of whose entries is a polynomial in the ring $R_q = \mathbb{Z}_q/(X^n+1)$
I am not entirely sure how to read this notation:
- Is this simply the polynomials of maximum degree where all coefficients are in $Z_q$?
- How is the multiplication of two polynomials defined in this ring?
- Does the matrix $\bf{A}$ now consist of $l$ polynomials or $k \times l$ polynomials?
$q$ is prime and $\mathbb{Z}_q=\mathbb{Z}/q\mathbb{Z}$ is the field with $q$ elements, $\mathbb{Z}_q[X]$ is the ring of polynomials with coefficients in $\mathbb{Z}_q$.
At first you can think to $R=\mathbb{Z}_q[X]/(X^n+1)$ as $\mathbb{Z}_q[X]$ quotiented by the relation $X^n=-1$. It means that in $\sum_{j=0}^J a_j X^j$ you can replace $X^j$ by $(-1)^{\lfloor j/n \rfloor} X^{j-n \lfloor j/n \rfloor}$, this gives for each polynomial a unique representative of degree $<n$.
Two such polynomials are added and multiplied as in $\mathbb{Z}_q[X]$, except that two elements of $R$ are equal iff they have the same representative of degree $<n$.
To clarify what is happening you should look first at $$\Bbb{C}\cong\Bbb{R}[X]/(X^2+1)$$ In $\Bbb{R}[X]$ quotiented by the relation $X^2=-1$ every element has a representative of the form $a+bX$ where $X$ is a square root of $-1$, so this is the complex numbers.
Finally $(X^2+1)$ means the ideal of $\Bbb{R}[X]$ generated by $X^2+1$, and the quotient of a ring $S$ by an ideal $I$ has a natural ring structure: its elements are subsets of $S$ of the form $u+I$ and $(u+I)+(v+I) =(u+v)+I$,$ (u+I)(v+I)=uv+I$.