Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n? For RLWE (Ring Learning With Errors) scheme, we use $R_{q} = \mathbb{Z}_{q}[x]/(x^{n} +1) = \mathbb{Z}_{q}[x]/(\Phi_{2n}(x))$ where $n = 2^{d}$ for some $d$. Since there exists $2n$-th root of unity in $\mathbb{Z}_{q}$ (which is the generator of the cyclic group $\mathbb{Z}_{q}^{\times}$), we can do FFT with the choice of the root of unity $\omega$ and do polynomial multiplication in $O(n\log n)$. Is there a way to apply FFT for primes $q \neq 1\,(\mathrm{mod}\,2n)$, so that there's no $2n$-th root of unity mod $q$?
Yes, in a way. When $q \neq 1 \mod 2n$ the ring $R_q$ is not fullt splitting (into polynomials of degree one). However, it might be splitting into several smaller polynomials of degree larger than one. Let $n &gt; d &gt; 1$ be powers of two such that $q$ is a prime and $q \equiv 1 + 2d \mod 4d$, then $X^n + 1$ splits into $d$ irreducible polynomials of the form $X^{n/d} + r_i$ modulo $q$ where $0 &lt; r_i &lt; q$ (see Corollary 1.2 in https://eprint.iacr.org/2017/523.pdf). Then you can use FFT to compute multiplication in $d$ levels, and then do it manually in the end. This can be as fast as full FFT (see e.g. https://eprint.iacr.org/2020/1397.pdf).