How to find the correct quotient ring $\mathbb{Z}[x]/p(x)$ (similar to $\mathbb{Z}[x]/(x^n-1)$)?

33 Views Asked by At

For the quotient ring $\mathbb{Z}[x]/(x^n-1)$, the product of two polynomials is like the following:

For $a=x^3-2x+1$ and $b=2x^3-2x^2+4x+3$, the product is $$c=ab=2x^6 - 2x^5 + 9x^3 - 10x^2 - 2x + 3,$$ and $c$ in $\mathbb{Z}[x]/(x^4-1)$ is $9x^3 - 8x^2 - 4x + 3$ because $$ 2x^6 - 2x^5 + 9x^3 - 10x^2 - 2x + 3 = (x^4-1)(2x^2-2x)+(9x^3 - 8x^2 - 4x + 3). $$

In $\mathbb{Z}[x]/(x^n-1)$, for two arrays $a=[a_0,a_1,\cdots, a_{m-1}]$ and $b=[b_0,b_1,\cdots,b_{m-1}]$, the product is

$$\begin{array}{rl} a*b=[&a_0b_{m-1}+\cdots+a_{m-1}b_0,\\ &(a_0b_0)+(a_1b_{m-1}+\cdots+a_{m-1}b_1),\\ &(a_0b_{1}+a_{1}b_0)+(a_{2}b_{m-1}+\cdots+a_{m-1}b_{2}),\\ &(a_0b_2+a_1b_1+a_2b_0)+(a_{3}b_{m-1}+\cdots+a_{m-1}b_{3}),\\ &\vdots\\ &(a_0b_{m-3}+\cdots+a_{m-3}b_0)+(a_{m-2}b_{m-1}+a_{m-1}b_{m-2}),\\ &(a_0b_{m-2}+\cdots+a_{m-2}b_0)+(a_{m-1}b_{m-1})] \end{array}$$

so for the previous example, $a=[1,0,-2,1]$ and $b=[2,-2,4,3]$ and the product is

$$ \begin{array}{rl} a*b=[&a_0b_{3}+a_1b_2+a_2b_1+a_{3}b_0,\\ &(a_0b_0)+(a_1b_{3}+a_2b_2+a_{3}b_1),\\ &(a_0b_{1}+a_{1}b_0)+(a_{2}b_{3}+a_{3}b_{2}),\\ &(a_0b_2+a_1b_1+a_2b_0)+(a_{3}b_{3})], \end{array} $$

which would yield

$$ \begin{array}{rl} a*b=[&1\times3+0\times4+(-2)\times(-2)+1\times2,\\ &(1\times 2)+(0\times 3+(-2)\times 4+1\times (-2)),\\ &(1\times (-2)+0\times 2)+((-2)\times 3+1\times 4),\\ &(1\times 4+0\times (-2)+(-2)\times 2)+(1\times 3)]\\ =&[9,-8,-4,3]\\ =&9x^3-8x^2-4x+3. \end{array} $$

Now I want to find $p(x)$ such that when working in $\mathbb{Z}[x]/p(x)$, then for these $a$ and $b$, we can get that

$$c\text{ (mod }p(x))=-8x^3-4x^2+3x+9=[-8,-4,3,9],$$ i.e., is almost the same result as for $\mathbb{Z}[x]/(x^4-1)$, but $1\mapsto x$, $x\mapsto x^2$, $x^2\mapsto x^3$ and $x^3\mapsto 1$.

In other words, for two arrays $a=[a_0,a_1,\cdots, a_{m-1}]$ and $b=[b_0,b_1,\cdots,b_{m-1}]$, we define the product as

$$\begin{array}{rl} a*b=[&(a_0b_0)+(a_1b_{m-1}+\cdots+a_{m-1}b_1),\\ &(a_0b_{1}+a_{1}b_0)+(a_{2}b_{m-1}+\cdots+a_{m-1}b_{2}),\\ &(a_0b_2+a_1b_1+a_2b_0)+(a_{3}b_{m-1}+\cdots+a_{m-1}b_{3}),\\ &\vdots\\ &(a_0b_{m-3}+\cdots+a_{m-3}b_0)+(a_{m-2}b_{m-1}+a_{m-1}b_{m-2}),\\ &(a_0b_{m-2}+\cdots+a_{m-2}b_0)+(a_{m-1}b_{m-1})\\ &a_0b_{m-1}+\cdots+a_{m-1}b_0] \end{array}$$

(like 'pushing' all the rows up and the original first row now is at the bottom), or in formula

$$(a*b)[j]=\sum_{i=0}^ja[i]b[j-i]+\sum_{i=j+1}^{m-1}a[i]b[m+j-i].$$

(I think its formal name is polynomial ring convolution)

Is there any known quotient ring where the residues follow this product rule?