Score:1

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

ca flag

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

poncho avatar
my flag
"Assuming formulas are correct..."; haven't we gone over this already? Those formulae are not correct (for example, they get $1 \cdot 1$ wrong)
fgrieu avatar
ng flag
[Trust, but verify](https://en.wikipedia.org/wiki/Trust,_but_verify) \[Russian proverb\]. Wolfram's Alpha [confirms](https://www.wolframalpha.com/input?i2d=true&i=PolynomialMod%5C%2891%29%5C%2840%29Power%5Bx%2C2%5D%2B2x%2B3%5C%2841%29%5C%2840%29Power%5Bx%2C2%5D%2Bx%5C%2841%29%5C%2844%29Power%5Bx%2C3%5D-1%5C%2893%29) 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](https://crypto.stackexchange.com/a/99906/555) another formula for the $x^n+1$ case, and most importantly how to derive it. Apply that methodology to the $x^n-1$ case.
user15651 avatar
ca flag
[poncho](https://crypto.stackexchange.com/users/452/poncho): I verified both formulas [you provided in](https://crypto.stackexchange.com/questions/99866/modular-reduction-in-the-ring-mathbbz-qx-xn-1/99906#99906). 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.
user15651 avatar
ca flag
[fgrieu](https://crypto.stackexchange.com/users/555/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. спасибо :)
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.