Модульная редукция в кольце $\mathbb{Z}_{q}[x]/(x^n + 1)$

Может кто-нибудь объяснить, как происходит сокращение? Я знаком с другими алгебраическими структурами, но мне интересно, правильно ли я делаю редукцию для этого.

Понятно, что полиномиальное кольцо этой формы, $\mathbb{Z}_{q}[x]/(x^n + 1)$, состоит из набора всех полиномов, определяемых формулой $(х^п + 1)$ с коэффициентами более $\mathbb{Z}_q = \{0, 1, ..., q-1\}$.

Для простоты скажем, что я работаю в $\mathbb{Z}_{5}[x]/[x^4+1]$

Скажем, я умножаю два многочлена в кольце по формуле свертки.

    3 2 1 0 <-- коэффициент indecis

$а(х) = 4х^3 + 1х^2 + 1х + 2$

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

$n=4, n-1=3$

вся арифметика коэффициентов выполняется по модулю 5 добавить лайки и уменьшить мод 5 отрицательные числа, мы добавляем кратные по модулю 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) $$

Три вопроса:

1. формула свертки верна.
2. вычитание похоже на обычные многочлены: $4x^2 - x^2 = 3x^2$
3. сокращение: делается как стандартное полиномиальное деление для получения остатка

Данный $(х^4 + 3х^3 + 3х^2 + х + 1) \mod (х^4 + 1)$: $\Rightarrow (x^4 + 3x^3 + 3x^2 + x + 1) / (x^4 + 1)$ первое вычитание: $\Rightarrow (x^4 + 3x^3 + 3x^2 + x + 1) - (x^4 + 1) = 3x^3 + 3x^2 + x$ (окончательный ответ)

Данный $(3x^5 + x^3 + 1) \mod (x^4 + 1) \Стрелка вправо (3x^5 + x^3 + 1) / 3x(x^4 + 1)$ первое вычитание: $\Стрелка вправо (3x^5 + x^3 + 1) - (3x^5 + 3x) = x^3 - 3x + 1)$

формула свертки верна.

Нет, это неправильно; если $ а = х ^ 0 $ и $б = х^0$, ваша формула даст $а \cdot б = 0$, что явно неверно.

Учебный способ выражения операции умножения:

$$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}$$

Эквивалентный способ (легко видно по тождеству $x^{k+n} \equiv -x^k \pmod{x^n+1}$ для любой $к$) является

$$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}$$

Я считаю, что последнее то, что вы имели в виду

вычитание похоже на обычные многочлены: $4x^2âx^2=3x^2$

Да (с той оговоркой, что, как вы сами упомянули, операции над коэффициентами производятся $\мод р$, в вашем примере $\мод 5$)

сокращение: делается как стандартное полиномиальное деление для получения остатка

Это можно сделать таким образом; вероятно, более эффективно использовать тождество, о котором я упоминал выше, т. $x^{k+n} \equiv -x^k \pmod{x^n+1}$)