為什麼在多項式乘法中使用負循環卷積而不是正常卷積？
當多項式從 $ \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) \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 $ 以一種直接的方式，沒有額外的複雜性？
用於構造密碼原語的潛在難題要求我們使用多項式環模 $ X^n + 1 $ .
例如，如果您的方案的安全性依賴於 RLWE，那麼您必須堅持使用使 RLWE 安全的環，這意味著您不能使用 $ X^n - 1 $ ，正如本答案中所討論的那樣。
Ring-SIS 問題也有同樣的情況。
一般來說，當你實例化任何問題時，你必須小心 $ X^n - 1 $ 作為模數，因為可以計算多項式 $ 1 $ 處理整數而不是多項式。例如，在本文的“多項式評估”部分對此進行了討論。