3
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Oct 30, 2023 at 6:16
  • 2
    $\begingroup$ @pod can you convert this comment into an answer? $\endgroup$
    – kelalaka
    Commented Oct 30, 2023 at 8:58

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Oct 30, 2023 at 19:35

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.