การลดโมดูลในวงแหวน $\mathbb{Z}_{q}[x]/(x^n + 1)$

ใครก็ได้ช่วยอธิบายหน่อยว่าการลดทำอย่างไร ฉันคุ้นเคยกับโครงสร้างพีชคณิตอื่น ๆ แต่สงสัยว่าฉันกำลังลดขนาดอย่างถูกต้องหรือไม่

เป็นที่เข้าใจกันว่า Polynomial Ring ของรูปแบบนี้ $\mathbb{Z}_{q}[x]/(x^n + 1)$, ประกอบด้วยเซตของพหุนามทั้งหมดที่กำหนดโดย $(x^n + 1)$ ด้วยค่าสัมประสิทธิ์มากกว่า $\mathbb{Z}_q = \{0, 1, ..., q-1\}$.

พูดง่ายๆ ว่าฉันกำลังทำงานอยู่ $\mathbb{Z}_{5}[x]/[x^4+1]$

สมมติว่าฉันคูณพหุนามสองตัวในวงแหวนตามสูตรการบิด

    3 2 1 0 <-- สัมประสิทธิ์ดัชนี

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

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

$n=4, n-1=3$

เลขคณิตสัมประสิทธิ์ทั้งหมดเสร็จสิ้น mod 5 เพิ่มเงื่อนไขที่ชอบและลด mod 5 จำนวนลบ เราเพิ่มทวีคูณของ 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) $$

สามคำถาม:

1. สูตร Convolution ถูกต้อง
2. การลบก็เหมือนกับพหุนามปกติ: $4x^2 - x^2 = 3x^2$
3. การลดลง: ทำเหมือนการหารพหุนามมาตรฐานเพื่อให้ได้สารตกค้าง

ที่ให้ไว้ $(x^4 + 3x^3 + 3x^2 + x + 1) \mod (x^4 + 1)$: $\ลูกศรขวา (x^4 + 3x^3 + 3x^2 + x + 1) / (x^4 + 1)$ การลบครั้งแรก: $\ลูกศรขวา (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)$

สูตร Convolution ถูกต้อง

ไม่ มันไม่ถูกต้อง ถ้า $a = x^0$ และ $b = x^0$สูตรของคุณจะให้ $a \cdot b = 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}$ สำหรับใดๆ $k$) เป็น

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

ใช่ (มีข้อแม้ว่าอย่างที่คุณพูดถึง การดำเนินการในค่าสัมประสิทธิ์เสร็จสิ้นแล้ว $\mod p$ในตัวอย่างของคุณ $\mod 5$)

การลดลง: ทำเหมือนการหารพหุนามมาตรฐานเพื่อให้ได้สารตกค้าง

สามารถทำได้ด้วยวิธีนั้น มีแนวโน้มว่าจะมีประสิทธิภาพมากกว่าในการใช้ประโยชน์จากข้อมูลประจำตัวที่ฉันกล่าวถึงข้างต้น $x^{k+n} \equiv -x^k \pmod{ x^n+1 }$)