ตัวอย่างการคูณพหุนามใน $\mathbb{Z}_{}[x]/(x^{n} \pm 1)$

ให้คำจำกัดความต่อไปนี้สำหรับ $\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}\ ซ้าย (\bmod x^{n}-1\right) $$ ในทำนองเดียวกันสำหรับ $\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}\ ซ้าย (\bmod x^{n}+1\right) $$

รายละเอียดตัวอย่าง: ให้ $a(x) = x^{2} + 2x + 3$ และ $b(x) = x^{2} + x$

ตัวอย่างต่อไปนี้นำมาจากงานตีพิมพ์ สมมติว่าผู้เขียนใช้สูตรข้างต้นเพื่อคำนวณผลรวมสุดท้ายอย่างถูกต้อง:

ตัวอย่างที่ 1 บอกว่า: ใน $\mathbb{Z}[x]/(x^{3} - 1)$ ผลรวมที่ได้จากสูตรแรกจะได้รับเป็น $(5x^{2} + 3x) + (x + 3) = 5x^{2} + 4x + 6$.

คำถามที่ 1: 6 ได้มาอย่างไรในคำตอบสุดท้าย? ไม่ควร $5x^{2} + 4x + 3$? เพราะ $\mathbb{Z}[x]$ หมายความว่าเรากำลังทำงานกับพหุนามใน $x$ ซึ่งมีการกำหนดค่าสัมประสิทธิ์ไว้ $\mathbb{Z}$, เซตของจำนวนเต็มทั้งหมด

ตัวอย่างที่ 2: ใน $\mathbb{Z}[x]/(x^{3} + 1)$ ผลบวกจากสูตรที่สองคือ $(5x^{2} + 3x) - (x + 3) = 5x^{2} + 2x$.

คำถามที่ 2: ในทำนองเดียวกัน คำตอบที่ได้ไม่ควรจะเป็น $5x^{2} + 2x - 3$ เนื่องจากมีข้อจำกัดเกี่ยวกับค่าสัมประสิทธิ์ (เช่น เราไม่ได้ทำงานใน $\mathbb{Z}_q$ สำหรับบางที่ระบุ $คิว$).