Good–Thomas Fast Fourier Transform
Objectives
Let $R$ be a ring, $\calD = \set{0, \dots, d - 1 }$ be an index set, $q_\calD$ be $d$ coprime integers, $\calQ = \prod_{i \in \calD} q_i$, $\calI = \set{0, \dots, \calQ - 1}$ and $\calI_i = \set{0, \dots, q_i - 1}$ be index sets, and $x$ and $x_\calD$ be indeterminates.
- Then, we have the following isomorphism $\eta$ for \[ \frac{R[x]}{\ideal{x^\calQ - 1}} \cong \Otimes_{i \in \calD} \frac{R[x_i]}{\ideal{x_i^{q_i} - 1}} \] by sending $x$ to $\prod_{i \in \calD} x_i$.
- $x \mapsto \prod_{i \in \calD} x_i$ corresponds to the following isomorphism of NTTs \[ \left( \ba(x) \mapsto \ba(\omega_\calQ^\calI) \right) \cong \Otimes_{i \in \calD} \left( \ba_i(x_i) \mapsto \ba_i(\omega_{q_i}^{\calI_i}) \right) \] where $\omega_{q_i} = \omega_\calQ^{e_i}$ and $e_\calI$ is the system of idempotents realizing $n \equiv \sum_{i \in \calD} e_i (n \bmod q_i) \pmod{\calQ}$.
- $x^l \mapsto \prod_{i \in \calD} x_i$ for an $l$ coprime to $\calQ$ is also a choice of multi-dimensional transform.
- Ruritanian: choose $l = \left( \sum_{i \in \calD} \frac{\calQ}{q_i} \right)^{-1} \bmod \calQ$.
- As an isomorphism from a group algebra to a tensor product of associative algebras.