How to multiply polynomials in $\mathbb Z[x]/(x^n+1)$?

Question

Consider the ring

$$R_q=\mathbb Z_q[X]/(X^n + 1),$$

where $q\equiv 1 \bmod 2n$ and $n$ is a power of $2$.

This is the quotient ring where the cosets are represented by polynomials up to $n-1$ in order.

I'd like to compute $c = a · b \bmod (X^n + 1)$, where $a$ and $b$ are polynomials in this ring, using Wolfram Cloud, or Wolfram Alpha, or anything easy to use.

This is for comparing with some code that I'm writing, that does this using NTT (Fast Fourier Transform for rings).

Is it possible?

For example:

$$(1x^0 + 2x^1 + 3x^2 + 4x^3 + 5x^4 + 6x^5 + 7x^6 + 8x^7)*(2x^0 + 5x^1 + 8x^2 + 11x^3 + 14x^4 + 17x^5 + 20x^6 + 23x^7) \mbox{ mod ($x^8+1$)} = ?$$

(where q = large, here, so all the coefficients fit)

Answer 1

The command you want in the Wolfram language is PolynomialMod. See documentation here. PolynomialMod[(1x^0+2x^1+3x^2+4x^3+5x^4+6x^5+7x^6+8x^7) * (2x^0+5x^1+8x^2+11x^3+14x^4+17x^5+20x^6+23x^7) , {x^8+1,2}] will return x^2 + x^4 + x^5 after reducing first mod $x^8+1$, and then reducing coefficients mod $2$.

Answer 2

The result is $$ 2(162x^7 + 20x^6 - 87x^5 - 162x^4 - 208x^3 - 228x^2 - 225x - 202). $$ One can simply introduce the relation $x^8:=-1$ and then do the multiplication.