การคำนวณเมทริกซ์สำหรับการแปลงตามทฤษฎีจำนวน

ฉันคุ้นเคยกับ Fourier Transform และการคำนวณเมทริกซ์ DFT และ FFT สำหรับการคูณจำนวนเต็มอย่างรวดเร็ว อย่างไรก็ตาม นี่เป็นครั้งแรกที่ฉันทำงานร่วมกับ NTT โดยนำไปใช้กับวงแหวนพหุนามของแบบฟอร์ม $\mathbb{Z}_q[x]/x^{n} + 1$.

พูดสำหรับเล็ก q=5 และ $n$=2. องค์ประกอบของฉันประกอบด้วยพหุนามดีกรีมากที่สุด $n-1$ ด้วยค่าสัมประสิทธิ์ใน $\mathbb{Z}_{q}$. การคำนวณค่าสัมประสิทธิ์ทั้งหมดทำได้ใน $\mathbb{Z}_{q}$.

ตอนนี้จะได้รับ $n$-th รากฐานดั้งเดิมของความสามัคคี $w$: ฉันสามารถแสดง q = Nk + 1 = 22 + 1 ฉันสามารถให้ N=2 ขนาดตัวอย่าง NTT และ k=2 ฉันให้ r = 2 (เป็นรากดั้งเดิมของ q) ฉันสามารถคำนวณ w เป็น $w = r^k \pmod{q}= 4 \pmod{5} = 4$ และยืนยัน $w^{k} \equiv 1 \pmod{q}$. $4^{2} = 16 \pmod{q} = 1$

คำถามแรก: วิธีนี้จะได้รับ $w$ ถูกต้อง?

เมทริกซ์ 2 คูณ 2 ของฉันจะมีรูปแบบนี้:

\begin{เมทริกซ์} 1 & 1\ 1 & ว \end{เมทริกซ์}

ทีนี้ เพื่อพิจารณากำลังที่สูงกว่าของ w สมมติว่าเรากำลังทำงานกับวงแหวนที่ใหญ่กว่าและมีเมทริกซ์ขนาด 3 คูณ 3 ให้ NTT_matrix = \begin{เมทริกซ์} 1 & 1 & 1 \ 1 & w & w^2 \ 1 & w^2 & w^3 \ \end{เมทริกซ์}

คำถามที่สอง: ในการคำนวณเมทริกซ์ย้อนกลับ ให้ NTT_inv_matrix =

\begin{เมทริกซ์} 1 & 1 & 1 \ 1 & w & w^{-2} \ 1 & w^{-2} & w^{-3} \ \end{เมทริกซ์}

คูณด้วย $N^{-1}$.

เพื่อคำนวณพลังด้านลบของ $w$, ผมหาผกผันการคูณของ องค์ประกอบที่เกี่ยวข้องในเมทริกซ์ไปข้างหน้าและคูณด้วย $N^{-1}$ (ผลคูณผกผันของขนาดตัวอย่าง $N$)?

ตัวอย่างเช่น สมมติว่าฉันมีรายการนี้ในเมทริกซ์ไปข้างหน้า: $w^3 = 4^3 \pmod{5} = 64 \pmod{5} = 4$ องค์ประกอบที่เกี่ยวข้องในเมทริกซ์ย้อนกลับจะเป็น $w^-3$. ในการคำนวณก็เหมือนกับ $(w^{3})^{-1}\pmod{5}$? ในกรณีนี้ผกผันการคูณ, MI, ของ $w^3\pmod{5}$ ก็จะเป็น 4 ตั้งแต่นั้นมา $4*4 \equiv 1 \pmod{5}$. และ MI(N) ใน mod 5 คือ 3 ตั้งแต่นั้นมา $3*2 \equiv 1 \pmod{5}$. จึงจะคำนวณได้ $w^{-3} = MI(w^{3})*MI(N) = 4 * 3 = 12 \pmod{5} = 2$?

คำถามที่สาม: หลังจากที่ฉันเติมเมทริกซ์ทั้งสองแล้ว ฉันก็สามารถคูณพหุนาม a(x) และ b(x) ได้โดยใช้ค่าสัมประสิทธิ์ทูเพิลของพวกมัน สำหรับแต่ละพหุนาม ฉันดำเนินการดังนี้: ถ้า a(x) = x + 3 = (a1=1, a0=3) ดังนั้นทูเพิลของมันก็คือ v = (1, 3) ฉันสามารถใช้การแปลงผ่านการคูณเมทริกซ์-เวกเตอร์ v*NTT_matrix = v. เช่นเดียวกับ b(x) บอกว่าฉันได้ v2. จากนั้น v3 = v`*v2 และสุดท้าย คำตอบ = NTT_inv_matrix(v3) ถูกต้อง?

คำถามที่สี่: สิ่งนี้ควรให้คำตอบเดียวกันกับการคูณ a(x)b(x) ด้วยมาตรฐาน สูตรการบิด ถูกต้อง ?

คำถามที่ห้า เพื่อกำหนดวงแหวนดังกล่าว $\mathbb{Z}_q[x]/x^{n} + 1$มันเป็นสิ่งจำเป็นที่ $คิว$ เป็นจำนวนเฉพาะเพื่อให้แน่ใจว่าการผกผันการคูณสำหรับองค์ประกอบทั้งหมดยกเว้น 0 และเช่นกัน $x^{n} + 1$ จะต้องลดไม่ได้ใน $\pmod{q}$, ถูกต้อง?

คำตอบสำหรับคำถามทั้งหมดของคุณคือใช่ ยกเว้นข้อสุดท้าย

หนึ่งสามารถใช้ $คิว$ ไม่เป็นไพรม์และใช้แหวน ภายใต้เงื่อนไขบางประการ การดำเนินการนี้จะทำให้คุณสามารถประเมิน NTT สำหรับความยาวทั่วไปมากขึ้นได้ $N.$

การแปลงทางทฤษฎีจำนวนอาจเป็นโมดูโลที่มีความหมาย $คิว$, แม้ว่าโมดูลัสจะไม่เป็นจำนวนเฉพาะ แต่ให้รูทหลักของคำสั่ง $N$ มีอยู่.

ตัวอย่างคือการแปลงหมายเลขแฟร์มาต์ด้วย $q= 2^k+1$ และ Mersenne Number Transform กับ $q= 2^k-1$.