# Understanding $\mathbb{Z}_q[X]/(X^N + 1)$ notation in cryptography paper

I can't seem to understand what $$A_{N,q}$$ represents in this paper (Section 2.1 - Notations). More specifically, I'm struggling to grasp the meaning of $$\mathbb{Z}_q[X]/(X^N + 1)$$. Could someone please explain it to me?

$$\lfloor . \rfloor$$ represents the ceiling function.

$$\mathbb Z_q = \mathbb Z \cap [-\lfloor\frac{q}{2}\rfloor, \lfloor\frac{q}{2}\rfloor]$$ for $$q \ge 2$$.

For a 2-power number $$N$$, and $$q > 0$$, we write $$A_{N,q}$$ to denote the set of integer polynomials $$A_{N,q} = \mathbb{Z}_q[X]/(X^N + 1)$$.

• It is the ring of polynomials (in indeterminate X) over the field Z_q (integers modulo q), modulo the polynomial X^N + 1 where N is some power of 2. It is a cyclotomic ring that frequently shows up in Ring-LWE and other hard lattice problems over Rings due to its admittance of fast Ring operations using FFT-like techniques. Commented Oct 30, 2023 at 6:16
• @pod can you convert this comment into an answer? Commented Oct 30, 2023 at 8:58

I'm struggling to grasp the meaning of $$\mathbb{Z}_q[X]/(X^N + 1)$$

Apologies if I'm coming at this at an overly basic level - I'm not sure where in your mathematical studies you are, and so I thought it would be better to underestimate your initial understanding...

This stands for a specific mathematical ring, that is, a set of values with addition and multiplication operations defined (that meet certain properties).

To see what ring it is, let us break it down:

• $$\mathbb{Z}_q$$

That's the ring of integers modulo $$q$$. That is, it is the integers, except that we consider two integers $$a, b$$ to be the same if $$a-b = kq$$ for some integer $$k$$.

We normally represent values in such a ring as values between 0 and $$q-1$$; however the paper specifically cites that they will be using the alternative representation of values between $$-\lfloor q/2 \rfloor$$ and $$\lfloor q/2 \rfloor$$. This alternative representation doesn't change the mathematical properties of the ring; however it may be important if they do operations that depend on the specific values.

• $$\mathbb{Z}_q[X]$$

This is the ring of polynomials over a single artificial variable $$X$$, where all the coefficients of the polynomial are members of the ring $$\mathbb{Z}_q$$.

Members of this ring include $$X^2 + 2 \cdot X + 1$$ and $$X^{19} - 7 X^{5}$$ (given that $$1, 2$$, and $$-7$$ are members of $$\mathbb{Z}_q$$.

Addition and multiplication in this ring is defined pretty much like addition and multiplication of polynomials over the reals, except that coefficient computations are done using $$\mathbb{Z}_q$$ operations.

• $$\mathbb{Z}_q[X]/(X^N + 1)$$

This is the above ring modulo the polynomial $$X^N+1$$. That is, we consider two polynomials $$P(X)$$ and $$Q(X)$$ to be the same if $$P(X) - Q(X) = R(X) \times (X^N+1)$$ for some polynomial $$R(X)$$ in $$\mathbb{Z}_q[X]$$.

With this ring, for any polynomial $$P(X)$$, there will be a unique polynomial $$Q(X)$$ of degree at most $$N-1$$ where $$P(X) = Q(X)$$ (using the above criteria). It is easy to find this polynomial $$Q(X)$$, and so is usually used as the canonical representation.

As mentioned in the comments, such a ring is called a cyclotomic ring, and has a number of interesting properties I won't delve into - this should give you both a taste and a direction to do more study, should you want to.

• Addition: The answer's polynomial $Q(X)\in\mathbb{Z}_q[X]/(X^N+1)$ can be represented by the vector of $N$ integers in $\bigl[-\left\lfloor q/2\right\rfloor,\left\lfloor q/2\right\rfloor\bigr]$ of the coefficients of Q[X] (e.g. from constant term to coefficient of the term of degree $N-1$). A computer implementation would do that. The set $\mathbb{Z}_q[X]/(X^N+1)$ has $q^N$ elements.
– fgrieu
Commented Oct 30, 2023 at 19:35