Note that the FFT has this property of “convolution is pointwise multiplication” for any cyclic multiplicative group, see https://www.sciencedirect.com/science/

Note that the FFT has this property of “convolution is pointwise multiplication” for any cyclic multiplicative group, see https://www.sciencedirect.com/science/article/pii/S0022000071800144 https://www.sciencedirect.com/science/article/pii/S002200007... for a more algebraic derivation. Some call this a “harmonic” fft, and there are also non-harmonic FFTs: - the “additive NTT” of [LCH14] on GF(2^n) - the circle fft on the unit circle X^2+Y^2=1 of a finite field [HLP24] - the ecfft on a sequence of elliptic curve isogenies [BCKL21] [LCH14]: https://arxiv.org/abs/1404.3458 https://arxiv.org/abs/1404.3458 [HLP24]: https://eprint.iacr.org/2024/278 https://eprint.iacr.org/2024/278 [BCKL21]: https://arxiv.org/pdf/2107.08473 https://arxiv.org/pdf/2107.08473