# Examples with Polynomial Multiplication in $\mathbb{Z}_{𝑞}[x]/(x^{n} \pm 1)$

Given the following definitions for $$\mathbb{Z}[x] /\left(x^{n}-1\right)$$:

$$a \cdot b \equiv \sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} a_{i} \cdot b_{j} \cdot x^{i+j}+\sum_{j=1}^{n-1} \sum_{i=n-j}^{n-1} a_{i} \cdot b_{j} \cdot x^{i+j-n}\left(\bmod x^{n}-1\right)$$ Similarly, for $$\mathbb{Z}[x] /\left(x^{n}+1\right)$$ the multiplication is defined as $$a \cdot b \equiv \sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} a_{i} \cdot b_{j} \cdot x^{i+j}-\sum_{j=1}^{n-1} \sum_{i=n-j}^{n-1} a_{i} \cdot b_{j} \cdot x^{i+j-n}\left(\bmod x^{n}+1\right)$$

An examples details: Let $$a(x) = x^{2} + 2x + 3$$ and $$b(x) = x^{2} + x$$

The following examples are taken from a published work. Assuming the author used the above formulas to compute the final sums correctly:

Example 1 says that: In $$\mathbb{Z}[x]/(x^{3} - 1)$$ resulting sums from first formula are given as $$(5x^{2} + 3x) + (x + 3) = 5x^{2} + 4x + 6$$.

Question 1: How is 6 obtain in final answer? should it not be $$5x^{2} + 4x + 3$$? because $$\mathbb{Z}[x]$$ means we are working with polynomials in $$x$$ whose coefficients are defined over $$\mathbb{Z}$$, the set of all integers.

Example 2: In $$\mathbb{Z}[x]/(x^{3} + 1)$$ resulting sums from second formula are $$(5x^{2} + 3x) - (x + 3) = 5x^{2} + 2x$$.

Question 2: Similarly, should the resulting answer not be $$5x^{2} + 2x - 3$$ since there is restriction on the coefficients (e.g., we are not working in $$\mathbb{Z}_q$$ for some specified $$q$$).

• "Assuming formulas are correct..."; haven't we gone over this already? Those formulae are not correct (for example, they get $1 \cdot 1$ wrong) Commented May 4, 2022 at 3:34
• Trust, but verify [Russian proverb]. Wolfram's Alpha confirms that $(x^2+2x+3)(x^2+x)\bmod(x^3-1)=5x^2+4x+3$; same for $(x^2+2x+3)(x^2+x)\bmod(x^3+1)=5x^2+2x-3$. Poncho gave another formula for the $x^n+1$ case, and most importantly how to derive it. Apply that methodology to the $x^n-1$ case.
– fgrieu
Commented May 4, 2022 at 5:26
• poncho: I verified both formulas you provided in. The point of the questions here is not the formulas, but the $\pm$ of the computed sums…(“assuming correct formulas”) I took the formulas and examples from the same published work; provided them only for background. I questioned if author overlooked something or if I was missing something. Commented May 4, 2022 at 6:17
• fgrieu Many many thanks for helping confirm with the Wolfram verification. I just learned 3 new things: sweet Russian proverb, new useful Wolfram Alpha math input to verify Polynomial Modular Arithmetic, and how to derive the $x^{n} - 1$ case. спасибо :) Commented May 4, 2022 at 6:25