เหตุใดจึงใช้การบิดเกลียวแบบเนกาไซคลิกสำหรับการคูณพหุนามแทนการบิดแบบปกติ

เมื่อคูณพหุนามจาก $\mathbb{Z}_q[X] / (X^n-1) $มีการใช้ NTT แบบแยกเนื่องจาก: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \right )$$ อย่างไรก็ตาม ในแทบทุกรูปแบบที่ฉันเคยเห็นมา เนกาไซคลิก ใช้การบิด - วงแหวนคือ $\mathbb{Z}_q[X] / (X^n+1) $ และใช้เล่ห์เหลี่ยมในการคำนวณ $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right ) \ขวา) $ โดยใช้ $\mathsf{NTT}_n$ เพราะเราต้องคูณพหุนามเข้าไป $\mathbb{Z}_q[X] / (X^{2n}-1) $.
คำถามของฉันคือ - ทำไมต้องกังวลด้วย $\mathbb{Z}_q[X] / (X^n+1) $ และไม่เพียงแค่ใช้ $\mathbb{Z}_q[X] / (X^n-1) $จึงสมัคร $\mathsf{NTT}_n$ ด้วยวิธีที่ตรงไปตรงมาโดยไม่มีข้อยุ่งยากเพิ่มเติม?

คุณระบุ (ฉันได้แก้ไขสัญกรณ์ของคุณแล้ว คลาสที่เหลือจะถูกนำด้วย a $/$ ไม่ $\แบ็กสแลช)$ อดีตคือ setminus ซึ่งไม่เหมือนกัน:

อย่างไรก็ตาม ในแทบทุกรูปแบบที่ฉันเคยเห็นมา เนกาไซคลิก ใช้การบิด - วงแหวนคือ $\mathbb{Z}_q[X] / (X^n+1) $ และใช้เล่ห์เหลี่ยมในการคำนวณ $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right ) \ขวา) $ โดยใช้ $\mathsf{NTT}_n$ เพราะเราต้องคูณพหุนามเข้าไป $\mathbb{Z}_q[X] / (X^{2n}-1) $.

และถามคำถาม:

ทำไมต้องยุ่งกับ $\mathbb{Z}_q[X] / (X^n+1) $ และไม่เพียงแค่ใช้ $\mathbb{Z}_q[X] \setminus (X^n-1) $?

ถ้าเรามีการแยกตัวประกอบพหุนาม $x^{2n}-1=(x^n-1)(x^n+1)$ จากนั้นทำการคำนวณแบบโมดูโล $x^{2n}-1$ สามารถเร่งความเร็วได้โดยการหมุนเวียน (ผ่าน NTT) ตามปัจจัยแต่ละอย่างแล้วรวมกัน ดังนั้น

1. เรามีการแยกตัวประกอบที่นำไปสู่การแปลงอย่างรวดเร็ว เราจึงใช้เส้นทางนี้ กรณีที่รุนแรงคือ FFT ที่ซับซ้อนเมื่อเราสามารถแยกตัวประกอบเป็นตัวประกอบเชิงเส้นได้ทั้งหมด $x^n-1=\prod_{i=1}^n (\omega^i-1)$ กับ $\โอเมก้า$ ดั้งเดิม $n^{th}$ รากของความสามัคคี
2. การแยกตัวประกอบนั้นไม่ซ้ำกัน คุณใช้ไม่ได้ $(x^n+1)$ ตั้งแต่นั้นเป็นต้นมา $(x^n+1)^2=(x^{2n}+2 x^n+1)$ และ $คิว$ โดยทั่วไปไม่ใช่ลักษณะ 2 ถ้าคุณหมายถึงจริง ๆ ก็แค่ใช้ $x^{2n}-1$ โดยตรง คุณจะไม่มีการเร่งความเร็ว