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

  • 2
    $\begingroup$ "Assuming formulas are correct..."; haven't we gone over this already? Those formulae are not correct (for example, they get $1 \cdot 1$ wrong) $\endgroup$
    – poncho
    Commented May 4, 2022 at 3:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented May 4, 2022 at 5:26
  • $\begingroup$ 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. $\endgroup$
    – user15651
    Commented May 4, 2022 at 6:17
  • $\begingroup$ 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. спасибо :) $\endgroup$
    – user15651
    Commented May 4, 2022 at 6:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.