Editing Prime-factor FFT algorithm (section)

=== Mapping based on CRT ===

For a coprime factorization {{tmath|1= \textstyle n = \prod_{d = 0}^{D - 1} n_d }}, we have the [[Chinese remainder theorem|Chinese remainder map]] <math>m \mapsto (m \bmod n_d)</math> from <math>\mathbb{Z}_{n}</math> to <math display="inline">\prod_{d = 0}^{D - 1} \mathbb{Z}_{n_d} </math> with <math display="inline">(m_d) \mapsto \sum_{d = 0}^{D - 1} e_d m_d</math> as its inverse where {{tmath|1= e_d }}'s are the [[central idempotent|central orthogonal idempotent elements]] with <math display="inline">\sum_{d = 0}^{D - 1} e_d = 1 \pmod{n}</math>.
Choosing <math>\omega_{n_d} = \omega_n^{e_d}</math> (therefore, {{tmath|1= \prod_{d = 0}^{D - 1} \omega_{n_d} = \omega_n^{\sum_{d = 0}^{D - 1} e_d} = \omega_n }}), we rewrite <math>\text{DFT}_{\omega_n}</math> as follows:

<math display="block">\hat{a}_j = 
\sum_{i = 0}^{n - 1} a_i \omega_n^{ij} = 
\sum_{i = 0}^{n - 1} a_i \left( \prod_{d = 0}^{D - 1} \omega_{n_d} \right)^{ij} = 
\sum_{i = 0}^{n - 1} a_i \prod_{d = 0}^{D - 1} \omega_{n_d}^{ (i \bmod n_d) (j \bmod n_d)} = 
\sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1} = 0}^{n_{D - 1} - 1} a_{\sum_{d = 0}^{D - 1} e_d i_d} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d (j \bmod n_d)} .</math>

Finally, define <math>a_{i_0, \dots, i_{D - 1}} = a_{\sum_{d = 0}^{D - 1} i_d e_d}</math> and {{tmath|1= \hat{a}_{j_0, \dots, j_{D - 1} } = \hat{a}_{\sum_{d = 0}^{D - 1} j_d e_d} }}, 
we have

<math display="block">\hat{a}_{j_0, \dots, j_{D - 1}} = \sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1}=0}^{n_{D - 1} - 1} a_{i_0, \dots, i_{D - 1}} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d j_d} .</math>

Therefore, we have the multi-dimensional DFT, {{tmath|1= \textstyle \otimes_{d = 0}^{D - 1} \text{DFT}_{\omega_{n_d} } }}.