Editing Prime-factor FFT algorithm (section)

=== Counting the number of multi-dimensional transformations ===
Notice that the condition for transforming <math>\text{DFT}_{\omega_n}</math> into <math display="inline">\eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d}} \circ \eta^*</math> relies on "an" additive group isomorphism <math>\eta</math> from <math>(\mathbb{Z}_n, +, 0)</math> to {{tmath|1= \textstyle \prod_d (\Z_{n_d}, +, 0) }}.
Any additive group isomorphism will work.
To count the number of ways transforming <math>\text{DFT}_{\omega_n}</math> into {{tmath|1= \textstyle \eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d} } \circ \eta^* }},
we only need to count the number of additive group isomorphisms from <math>(\mathbb{Z}_n, +, 0)</math> to <math display="inline">\prod_d (\mathbb{Z}_{n_d}, +, 0)</math>, or alternative, the number of additive group [[automorphism]]s on {{tmath|1= (\Z_n, +, 0) }}.
Since <math>(\mathbb{Z}_n, +, 0)</math> is [[Cyclic group|cyclic]], any automorphism can be written as <math>1 \mapsto g</math> where <math>g</math> is a [[Cyclic group|generator]] of <math>(\mathbb{Z}_n, +, 0)</math>.
By the definition of {{tmath|1= (\Z_n, +, 0) }}, <math>g</math>'s are exactly those coprime to <math>n</math>.
Therefore, there are exactly <math>\varphi(n)</math> many such maps where <math>\varphi</math> is the [[Euler's totient function]].
The smallest example is <math>n = 6</math> where <math>\varphi(n) = 2</math>, demonstrating the two maps in the literature: the "CRT mapping" and the "Ruritanian mapping".<ref>{{harvnb|Good|1971}}</ref>