Cómo multiplicar polinomios en $\mathbb Z[x]/(x^n+1)$ ?

Question

Considere el anillo

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

donde $q\equiv 1 \bmod 2n$ y $n$ es una potencia de $2$ .

Este es el anillo cociente donde los cosets están representados por polinomios hasta $n-1$ en orden.

Me gustaría calcular $c = a · b \bmod (X^n + 1)$ , donde $a$ y $b$ son polinomios en este anillo, usando Wolfram Cloud, o Wolfram Alpha, o cualquier cosa fácil de usar.

Esto es para comparar con un código que estoy escribiendo, que hace esto usando NTT (Transformada rápida de Fourier para anillos).

¿Es posible?

Por ejemplo:

$$(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 $)} = ?$$

(donde q = grande, aquí, para que todos los coeficientes encajen)

Answer 1

El comando que quieres en el lenguaje Wolfram es PolynomialMod. Véase la documentación aquí . PolinomioMod[(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}] devolverá x^2 + x^4 + x^5 después de reducir el primer mod $x^8+1$ y luego reduciendo los coeficientes mod $2$ .

Answer 2

El resultado es $$ 2(162x^7 + 20x^6 - 87x^5 - 162x^4 - 208x^3 - 228x^2 - 225x - 202). $$ Se puede introducir simplemente la relación $x^8:=-1$ y luego hacer la multiplicación.