Reducere modulară în inel $\mathbb{Z}_{q}[x]/(x^n + 1)$

Poate cineva să explice cum se face reducerea? Sunt familiarizat cu alte structuri algebrice, dar mă întreb dacă reduc corect pentru asta.

Se înțelege că un inel polinomial de această formă, $\mathbb{Z}_{q}[x]/(x^n + 1)$, constă din mulțimea tuturor polinoamelor definite de $(x^n + 1)$ cu coeficienţi peste $\mathbb{Z}_q = \{0, 1, ..., q-1\}$.

Pentru simplitate, să spunem că lucrez $\mathbb{Z}_{5}[x]/[x^4+1]$

Să presupunem că înmulțesc două polinoame în inel conform formulei de convoluție.

    3 2 1 0 <-- coeficient indecis

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

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

$n=4, n-1=3$

toată aritmetica coeficienților se face mod 5 adăugați termeni similari și reduceți modul 5 numere negative, adunăm multipli ai modului 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) $$

Trei intrebari:

1. formula de convoluție este corectă.
2. scăderea este ca polinoamele normale: $4x^2 - x^2 = 3x^2$
3. reducere: se face ca o împărțire polinomială standard pentru a obține reziduu

Dat $(x^4 + 3x^3 + 3x^2 + x + 1) \mod (x^4 + 1)$: $\Săgeată la dreapta (x^4 + 3x^3 + 3x^2 + x + 1) / (x^4 + 1)$ prima scadere: $\Săgeată la dreapta (x^4 + 3x^3 + 3x^2 + x + 1) - (x^4 + 1) = 3x^3 + 3x^2 + x$ (răspuns final)

Dat $(3x^5 + x^3 + 1) \mod (x^4 + 1) \Săgeată la dreapta (3x^5 + x^3 + 1) / 3x(x^4 + 1)$ prima scadere: $\Săgeată la dreapta (3x^5 + x^3 + 1) - (3x^5 + 3x) = x^3 - 3x + 1)$

formula de convoluție este corectă.

Nu, nu este corect; dacă $a = x^0$ și $b = x^0$, formula ta ar da $a \cdot b = 0$, ceea ce este evident greșit.

Modul manual de exprimare a operației de înmulțire este:

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

O modalitate echivalentă (cu ușurință de văzut de identitate $x^{k+n} \equiv -x^k \pmod{x^n+1}$ pentru orice $k$) este

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

Cred că acesta din urmă este ceea ce ai vrut

scăderea este ca polinoamele normale: $4x^2âx^2=3x^2$

Da (cu avertismentul că, așa cum ați menționat însuți, operațiile în coeficienți sunt făcute $\mod p$, în exemplul tău, $\mod 5$)

reducere: se face ca o împărțire polinomială standard pentru a obține reziduu

Se poate face așa; este probabil mai eficient să profităm de identitatea pe care am menționat-o mai sus, că $x^{k+n} \equiv -x^k \pmod{ x^n+1 }$)