Implementation
如果 q 不是 1 模 2n，則 FFT 是否可能用於二分圓環的冪？
對於 RLWE（帶錯誤的環學習）方案，我們使用 $ R_{q} = \mathbb{Z}{q}[x]/(x^{n} +1) = \mathbb{Z}{q}[x]/(\Phi_{2n}(x)) $ 在哪裡 $ n = 2^{d} $ 對於一些 $ d $ . 既然存在 $ 2n $ - 統一的根 $ \mathbb{Z}{q} $ （這是循環群的生成器 $ \mathbb{Z}{q}^{\times} $ )，我們可以用統一根的選擇來做 FFT $ \omega $ 並做多項式乘法 $ O(n\log n) $ . 有沒有辦法對素數應用 FFT $ q \neq 1,(\mathrm{mod},2n) $ ，所以沒有 $ 2n $ -unity mod 的根 $ q $ ?
是的，在某種程度上。什麼時候 $ q \neq 1 \mod 2n $ 戒指 $ R_q $ 不是完全分裂（成一階多項式）。但是，它可能會拆分為多個次數大於一的較小多項式。讓 $ n > d > 1 $ 是二的冪，使得 $ q $ 是一個素數並且 $ q \equiv 1 + 2d \mod 4d $ ， 然後 $ X^n + 1 $ 分裂成 $ d $ 形式的不可約多項式 $ X^{n/d} + r_i $ 模組 $ q $ 在哪裡 $ 0 < r_i < q $ （參見https://eprint.iacr.org/2017/523.pdf中的推論 1.2 ）。然後你可以使用 FFT 來計算乘法 $ d $ 水平，然後在最後手動完成。這可以與完整的 FFT 一樣快（參見例如https://eprint.iacr.org/2020/1397.pdf）。