# DFT decomposition Let $V_0=U_0\cdot R=\bigg(\ \omega_{4n}^{5^i\cdot \text{bitrev}_n(j)\bmod n}\bigg)_{i,j=0}^{n/2}$ where $U_0$ defined [[Canonical mapping (CKKS encoding)|here]] and $R$ is the bit reverse permutation. note that multiplication by bitrev is equivalent to start with $U_0$ and permute the columns according to the bot reverse permutation. Let define $S_n=\bigg(\ \omega_{4n}^{5^i\cdot \text{bitrev}_n(j)\bmod n}\bigg)_{i,j=0}^{n/2}$ and $W_n=\text{diag}(\omega_{4n}^{5^i\bmod n})_{i=0}^n$. It satisfies $ S_n= \begin{bmatrix} I_n & W_n \\ I_n & -W_n \end{bmatrix} \cdot \begin{bmatrix} S_{n-1} & 0 \\ 0 & S_{n-1} \end{bmatrix} $ and so we get $V_0=E_2^{(n/2)}\cdot E_4^{(n/2)}\cdots E_{n/2}^{(n/2)}$ where, $E_{k}^{n}= \begin{bmatrix} \begin{bmatrix} I_{n/k} & W_{n/k} \\ I_{n/k} & -W_{n/k} \end{bmatrix} & 0 & \cdots & 0 \\ 0 & \begin{bmatrix} I_{n/k} & W_{n/k} \\ I_{n/k} & -W_{n/k} \end{bmatrix} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0& \cdots & \begin{bmatrix} I_{n/k} & W_{n/k} \\ I_{n/k} & -W_{n/k} \end{bmatrix} \end{bmatrix} $ ## References - [[@Computational Frameworks for the Fast Fourier Transform (Frontiers in Applied Mathematics)]], p.37 Theorem 1.2.1. and section 1.3.3 - [[@Improved Homomorphic DFT and FHE Bootstrapping]], p.5 and p.8 lemma 5. #math ## Created 2025-03-18 11:32