2
$\begingroup$

May someone please explain how the reduction is done? I am familiar with other algebraic structures but wondering if I am doing reduction correctly for this.

It is understood that a Polynomial Ring of this form, $\mathbb{Z}_{q}[x]/(x^n + 1)$, consists of the set of all polynomials defined by $(x^n + 1)$ with coefficients over $\mathbb{Z}_q = \{0, 1, ..., q-1\}$.

For simplicity, say I am working in $\mathbb{Z}_{5}[x]/[x^4+1]$

Say I multiply two polynomials in the ring according to the convolution formula.

enter image description here

    3      2      1   0 <-- coefficient indecis

$a(x) = 4x^3 + 1x^2 + 1x + 2$

$b(x) = 1x^3 + 1x^2 + 3x + 2$

$n=4, n-1=3$

all coefficient arithmetic is done mod 5 add like terms and reduce mod 5 negative numbers, we add multiples of mod 5

$$a(x)\cdot b(x) = ([(a_0b_1x + a_0b_2x^2 + a_0b_3x^3) + (a_1b_2x^3 + a_1b_3x^4 + a_2b_3x^3)] - \\ [a_3b_1 + a_2b_2 + a_3b_2x + a_1b_3 + a_2b_3x + a_3b_3x^2]) \mod (x^4 + 1)\\ =[(x + 2x^2 + x^3) + (x^3 + x^4 + x^3)] - [(2 + 1 + 4x + 1 + 1x + 4x^2)] \mod.. \\ = [x^4 + 3x^3 + 2x^2 + x] - [4x^2 + 4] \mod..\\ = [x^4 + 3x^3 + (2-4)x^2 + x - 4] \mod..\\ = [x^4 + 3x^3 + 3x^2 + x + 1] \mod (x^4 + 1) $$

Three questions:

  1. convolution formula is correct.
  2. subtraction is like normal polynomials: $4x^2 - x^2 = 3x^2$
  3. reduction: done like standard polynomial division to obtain residue

Given $(x^4 + 3x^3 + 3x^2 + x + 1) \mod (x^4 + 1)$: $\Rightarrow (x^4 + 3x^3 + 3x^2 + x + 1) / (x^4 + 1)$ first subtraction: $\Rightarrow (x^4 + 3x^3 + 3x^2 + x + 1) - (x^4 + 1) = 3x^3 + 3x^2 + x$ (final answer)

Given $(3x^5 + x^3 + 1) \mod (x^4 + 1) \Rightarrow (3x^5 + x^3 + 1) / 3x(x^4 + 1)$ first subtraction: $\Rightarrow (3x^5 + x^3 + 1) - (3x^5 + 3x) = x^3 - 3x + 1)$

$\endgroup$

1 Answer 1

3
$\begingroup$

convolution formula is correct.

No, it is not correct; if $a = x^0$ and $b = x^0$, your formula would give $a \cdot b = 0$, which is obviously wrong.

The textbook way to express the multiplication operation is:

$$a \cdot b = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} a_i \cdot b_j \cdot x^{i+j} \pmod{x^n+1}$$

An equivalent way (easily seen by the identity $x^{k+n} \equiv -x^k \pmod{x^n+1}$ for any $k$) is

$$a \cdot b = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1-i} a_i \cdot b_j \cdot x^{i+j} - \sum_{i=1}^{n-1} \sum_{j=n-i}^{n-1} a_i \cdot b_j \cdot x^{i+j-n}$$

I believe the latter is what you intended

subtraction is like normal polynomials: $4x^2−x^2=3x^2$

Yes (with the caveat that, as you yourself mentioned, the operations in the coefficients is done $\mod p$, in your example, $\mod 5$)

reduction: done like standard polynomial division to obtain residue

It can be done that way; it is likely more efficient to take advantage of the identity I mentioned above, that $x^{k+n} \equiv -x^k \pmod{ x^n+1 }$)

$\endgroup$
1
  • $\begingroup$ I took the formula provided from a PhD thesis. Searched it up on several university lectures and articles, none provided explicit formula with indecis. Some even listes this for the coefficients: $$c_i = {\sum_{j+k=i} a_j \cdot b_k - \sum_{j+k=n+i} a_j \cdot b_k }\pmod{q}$$ for coefficients of degree at most n-1. However, for the formula provided, when both polynomials have degree 0, the outer loop/sum conditions are not met and we never enter them. Thank you so much for the formulas you provided Poncho, I tried them out and get the same result for both. :) $\endgroup$
    – user15651
    Commented May 2, 2022 at 18:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.