Editing Prime-factor FFT algorithm (section)

=== As algebra isomorphisms ===
PFA can be stated in a high-level way in terms of [[Algebra homomorphism|algebra isomorphisms]].
We first recall that for a commutative ring <math>R</math> and a [[group isomorphism]] from <math>G</math> to {{tmath|1= \textstyle \prod_d G_d }}, we have the following algebra isomorphism

<math display="block">R[G] \cong \bigotimes_d R[G_d] ,</math>

where <math>\bigotimes</math> refers to the [[tensor product of algebras]].

To see how PFA works, we choose <math>G = (\Z_n, +, 0)</math> and <math>G_d = (\Z_{n_d}, +, 0)</math> be [[additive group]]s.
We also identify <math>R[G]</math> as <math display="inline">\frac{R[x]}{\langle x^n - 1 \rangle}</math> and <math>R[G_d]</math> as {{tmath|1= \textstyle \frac{R[x_d]}{\langle x_d^{n_d} - 1 \rangle} }}.
Choosing <math>\eta = a \mapsto (a \bmod n_d)</math> as the group isomorphism {{tmath|1= \textstyle G \cong \prod_d G_d }}, we have the algebra isomorphism <math display="inline">\eta^* : R[G] \cong \bigotimes_d R[G_d]</math>, or alternatively,

<math display="block"> \eta^* : \frac{R[x]}{\langle x^n - 1 \rangle} \cong \bigotimes_d \frac{R[x_d]}{\langle x_d^{n_d} - 1 \rangle} .</math>

Now observe that <math>\text{DFT}_{\omega_n}</math> is actually an algebra isomorphism from <math display="inline">\frac{R[x]}{\langle x^n - 1 \rangle}</math> to <math display="inline">\prod_i \frac{R[x]}{\langle x - \omega_n^i \rangle}</math> and each <math>\text{DFT}_{\omega_{n_d}}</math> is an algebra isomorphism from <math display="inline">\frac{R[x]}{\langle {x_d}^{n_d} - 1 \rangle}</math> to <math display="inline">\prod_{i_d} \frac{R[x_d]}{\langle x_d - \omega_{n_d}^{i_d} \rangle}</math>,
we have an algebra isomorphism <math>\eta'</math> from <math display="inline">\bigotimes_d \prod_{i_d} \frac{R[x_d]}{\langle x_d - \omega_{n_d}^{i_d} \rangle}</math> to <math display="inline">\prod_i \frac{R[x]}{\langle x - \omega_n^i \rangle}</math>.
What PFA tells us is that <math display="inline">\text{DFT}_{\omega_n} = \eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d}} \circ \eta^*</math> where <math>\eta^*</math> and <math>\eta'</math> are re-indexing without actual arithmetic in <math>R</math>.