Tại sao sử dụng tích chập âm cho phép nhân đa thức thay vì tích chập thông thường?

Khi nhân đa thức từ $\mathbb{Z}_q[X] / (X^n-1) $, NTT rời rạc được sử dụng vì: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \right ) $$ Tuy nhiên, trong hầu như tất cả các chương trình tôi đã thấy vòng âm tích chập được sử dụng - chiếc nhẫn là $\mathbb{Z}_q[X] / (X^n+1) $ và một thủ thuật được sử dụng để tính toán $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right ) \right) $ sử dụng $\mathsf{NTT}_n$ bởi vì chúng ta phải nhân các đa thức trong $\mathbb{Z}_q[X] / (X^{2n}-1) $.
Câu hỏi của tôi là - tại sao phải bận tâm với $\mathbb{Z}_q[X] / (X^n+1) $ và không chỉ đơn giản là sử dụng $\mathbb{Z}_q[X] / (X^n-1) $, do đó áp dụng $\mathsf{NTT}_n$ một cách đơn giản mà không có thêm biến chứng?

Bạn nêu (Tôi đã sửa ký hiệu của bạn, các lớp dư lượng được thực hiện bằng một $/$ không phải $\dấu gạch chéo ngược)$ cái trước là setminus không giống nhau:

Tuy nhiên, trong hầu như tất cả các chương trình tôi đã thấy vòng âm tích chập được sử dụng - chiếc nhẫn là $\mathbb{Z}_q[X] / (X^n+1) $ và một thủ thuật được sử dụng để tính toán $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right ) \right) $ sử dụng $\mathsf{NTT}_n$ bởi vì chúng ta phải nhân các đa thức trong $\mathbb{Z}_q[X] / (X^{2n}-1) $.

và đặt câu hỏi:

tại sao bận tâm với $\mathbb{Z}_q[X] / (X^n+1) $ và không chỉ đơn giản là sử dụng $\mathbb{Z}_q[X] \setminus (X^n-1) $?

Nếu chúng ta có nhân tử đa thức $x^{2n}-1=(x^n-1)(x^n+1)$ sau đó tính toán modulo $x^{2n}-1$ có thể được tăng tốc bằng cách tích hợp (thông qua NTT) đối với từng yếu tố và sau đó kết hợp. Cho nên

1. Chúng tôi có một hệ số hóa dẫn đến một sự biến đổi nhanh chóng, vì vậy chúng tôi đi theo con đường này. Trường hợp cực đoan là FFT phức tạp khi chúng ta có thể tính tất cả các yếu tố thành các yếu tố tuyến tính $x^n-1=\prod_{i=1}^n (\omega^i-1)$ với $\omega$ một nguyên thủy $n^{th}$ gốc của sự đoàn kết.
2. Hệ số hóa là duy nhất, bạn không thể sử dụng $(x^n+1)$ chỉ kể từ khi $(x^n+1)^2=(x^{2n}+2 x^n+1)$ và $q$ nói chung không phải là đặc điểm 2. Nếu bạn thực sự muốn sử dụng $x^{2n}-1$ trực tiếp, bạn sẽ không tăng tốc.