# NTT/INTT - The Number Theoretic Transform
> Nhan_laptop|
> ---
----

> Note: resouce chính: https://eprint.iacr.org/2024/585.pdf , https://www.nayuki.io/page/number-theoretic-transform-integer-dft

## Overvew

Mục đích của blog này sẽ giới thiệu cho các bạn một thuật toán mạnh mẽ giúp ta nhân 2 đa thức (trong trường số hữu hạn) với độ phức tạp giảm đi đáng kể so với các cách thông thường.
Ví dụ trực quan:
- Nhân 2 đa thức: $(x^2+ x + 3)\times ( x^2 + 1 ):$

\begin{aligned}
&\quad\ (x^2 + x + 3)\\
&\times\ (x^2 + 1)\\
&\underline{\hphantom{xxxxxxxxxxxxxxxx}}\\[-2pt]
&\quad\ (x^2 + x + 3) \qquad\text{(nhân với }1)\\
&x^2(x^2 + x + 3) \qquad\ \text{(nhân với }x^2)\\
&\underline{\hphantom{xxxxxxxxxxxxxxxx}}\\[-2pt]
&x^4 + x^3 + 4x^2 + x + 3
\end{aligned}

- note: mỗi phép nhân nhỏ được tính là 1 đơn vị chi phí.

Gốc nhìn tổng quát: cho 2 đa thức:
\begin{aligned}
A(x) &= a_0 + a_1 + \cdots a_{n-1}\cdot x^{n-1}\\
B(x) &= b_0 + b_1 + \cdots b_{n-1}\cdot x^{n-1}
\end{aligned}

Mục đích của chính ta là tính toán da thức $C(x) = A(x) \cdot B(x)$, nếu chúng ta nghĩ các hệ số của 2 đa thức $A,B$ như là một vector, thì C-vector được gọi là "**Tích chập - Convolution**" của $A,B$.
Dễ dàng tính được độ phức tạp của thuật toán trên là: O($n^2$).

Thuật toán NTT/INTT là một khái quát của DFT cổ điển làm việc trên modulo nguyên tố q có chứa gốc n-th primitive root of unity 𝜔. Kết quả chính xác trong $\mathbb{Z}_q$, làm giảm đáng kể độ phức tạp trong tính toán bằng cách ứng dụng Fast Fourier Transform-style algorithms.

## Review of the Discrete Fourier transform - DFT over a ring

### Definition
Đặt $R$ là một ring bất kì, với số nguyên $n \ge 1 $, ta có $\alpha \in R$, với $\alpha$ được gọi là **principal n-th roof of unity**, được dịnh nghĩa như sau:

\begin{array}{c}
\left\{
\begin{aligned}
\alpha ^ n & \equiv 1\\
\sum_{j=0} ^ {n-1} \alpha ^{j\cdot k} &\equiv 0\ \text{ for }1 \le k < n
\end{aligned}
\right.
\end{array}

The DFT ánh xạ một n-tuple $(v_0,\cdots,v_{n-1})$ các phần tử thuộc $R$ sang một n-tuple khác $(f_0,\cdots,f_{n-1}$ các phần tử cũng thuộc $R$ theo công thức:

$$
f_k = \sum_{j=0} ^ {n-1} v_j \cdot \alpha ^{j\cdot k}
$$

Theo quy ước, tuple $(v_0,\cdots,v_{n-1})$ được gọi là các phân tử time domain và các chỉ số $j$ được gọi là time. Tuple $(f_0,\cdots,f_{n-1}$ được gọi là các phần tử trong frequency domain và các chỉ số $k$ được gọi là frequency. Một cách gọi khác tuple $(f_0,\cdots,f_{n-1}$ là quang phổ-spectrum của $(v_0,\cdots,v_{n-1})$, thuật ngữ bắt nguồn từ cách phép biến đổi ứng dụng của Fourier transforms trong signal processing.

### Inverse - IDFT

Giá trị nghịch đảo của The DFT được tính như sau:

$$
v_j = \frac{1}{n}\cdot \sum_{k=0} ^ {n-1}f_{k}\cdot \alpha ^{-j\cdot k}
$$

Với $\frac{1}{n}$ là nghịch đảo của n trong $R$ (chú ý: nếu n không có nghịch đảo trong $R$ thì không thể thực hiện DFT).

:::info
**Proof**:
\begin{aligned}
&\ \frac{1}{n}\cdot \sum_{k=0} ^ {n-1}f_{k}\cdot \alpha ^{-j\cdot k}\\
&= \frac{1}{n}\cdot \sum_{k=0} ^ {n-1}
\sum_{j'=0} ^ {n-1} v_{j'} \cdot \alpha ^{j'\cdot k} \cdot \alpha ^{-j\cdot k}\\
&= \frac{1}{n} \sum_{j'=0} ^ {n-1} v_{j'} \cdot \sum_{k=0} ^ {n-1}
\cdot \alpha ^{(j'-j)\cdot k} \\
\end{aligned}

Ta có $\sum_{k=0} ^ {n-1} \cdot \alpha ^{(j'-j)\cdot k}\equiv 0$ khi $j'\neq j$ ( lúc này tổ hợp $(j'-j)\cdot k$ ta hoàn toàn có thể xếp tuần tự các giá trị giống như phần trên đã nói), và khi $j'=j \Rightarrow \sum_{k=0} ^ {n-1} \cdot \alpha ^{0}\equiv n$. Nên biểu thức trên sẽ bằng $v_j$.
:::

Vậy ta có một phép ánh xạ như sau:

\begin{aligned}
(v_0,\cdots,v_{n-1})\xrightarrow{DFT} (f_0,\cdots,f_{n-1})\\
(f_0,\cdots,f_{n-1})\xrightarrow{IDFT} (v_0,\cdots,v_{n-1})\\
\end{aligned}

### Matrix formulation

Ta hoàn toàn có thể biểu diễn phép biến đổi DFT ở dạng ma trận ( vì phép ánh xạ là các toán tử tuyến tính). Trong kí hiệu ma trận, DFT được biểu diễn như:

\begin{array}{c}
\begin{bmatrix}
f_0\\
f_1\\
\vdots\\
f_{n-1}
\end{bmatrix}=
\begin{bmatrix}
1 & 1 & 1 & \cdots & 1\\
1 & \alpha & \alpha^{2} & \cdots & \alpha^{\,n-1}\\
1 & \alpha^{2} & \alpha^{4} & \cdots & \alpha^{\,2(n-1)}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & \alpha^{\,n-1} & \alpha^{\,2(n-1)} & \cdots & \alpha^{\,(n-1)(n-1)}
\end{bmatrix}
\begin{bmatrix}
v_0\\
v_1\\
\vdots\\
v_{n-1}
\end{bmatrix}\,.
\end{array}

Dạng ma trận cho phép biến đổi này được gọi là DFT matrix.

Tương tự cho nghịch đảo DFT:

\begin{array}{c}
\begin{bmatrix}
v_0\\
v_1\\
\vdots\\
v_{n-1}
\end{bmatrix}=\frac{1}{n} \cdot
\begin{bmatrix}
1 & 1 & 1& \cdots & 1\\
1 & \alpha^{-1} &\alpha^{-2} & \cdots & \alpha^{-(n-1)}\\
1 & \alpha^{-2} &\alpha^{-3} & \cdots & \alpha^{-2(n-1)}\\
\vdots & \vdots &\vdots & \ddots & \vdots\\
1 & \alpha^{-(n-1)}& \alpha^{-2(n-1)} & \cdots & \alpha^{-(n-1)(n-1)}
\end{bmatrix}
\begin{bmatrix}
f_0\\
f_1\\
\vdots\\
f_{n-1}
\end{bmatrix}.
\end{array}

### Polynomial fomulation

Một cách nào đó ta có thể định nghĩa một tuple ($v_0,\cdots,v_{n-1}$) với một đa thức:

$$
p_v(x) = v_0 + v_1 \cdot x + v_2 \cdots x^2 + \cdot + v_{n-1}\cdot x^{n-1}.
$$

Nếu ta viết từng công thức của $f_k$:

$$
f_k = v_0 + v_1 \cdot \alpha ^ k + v_2 \cdot \alpha ^ {2k}+ \cdots + v_{n-1} \cdot \alpha ^ {(n-1)\cdot k} = \sum_{j=0} ^ {n-1} v_j \cdot \alpha ^{j\cdot k}
$$

Việc này tương đương đến $f_k$ là một giá trị của biểu thức $p_v(x)$ với $x=\alpha ^ k$:

$$
f_k = p_v (\alpha ^ k).
$$

:::warning
Vì vậy ta có thể hoàn toàn xem các hệ số và giá trị của đa thức là:
- Hệ số là phần tử trong time-domain,
- Giá trị là phần tử trong frequency domain.

Chú ý: Ta chỉ có thể biến đổi DFT trên đa thức, nếu nó được tính toán trên nth-root of unity, chính xác là số mũ của $\alpha$.
:::

Tương tự ta cũng có $p_f(x) = p_v^{-1}(x)$:

$$
p_f(x) = f_0 + f_1 \cdot x + f_2 \cdot x^2 + \cdots + f_{n-1}\cdot x^{n-1}.
$$

## NTT/INTT - The Number Theoretic Trbnsform

### Introduction

Trong blog này mình sẽ giới thiệu một số khái niệm cơ bản, bao gồm cả cài đặt thuật toán (Rust), giải thích một cách trực quan nhất có thể.

Note:
- NTT - The Number Theoretic Transform như DFT trong vòng đa thức.
- Cải tiến của NTT/INTT transformation bằng cách sử dụng the Fast - Fourier Transformation (FFT)- style calculation: The Cooley-Tukey (CT) và the Gentleman-Sande (GS) butterflies algorithm.
### Convolution

Như đã đề cập ở đầu blog, tích chập vòng - Convolution nghĩa là kết quả của phép tính giữa 2 đa thức.

### Cyclic Convolution

Cho 2 đa thức A(x) và B(x) có bậc là n-1 trong vành thương $\mathbb{Z}_q(x)/(x^n -1)$ với q số nguyên:

\begin{aligned}
A(x) &= a_0 + a_1 + \cdots a_{n-1}\cdot x^{n-1}\\
B(x) &= b_0 + b_1 + \cdots b_{n-1}\cdot x^{n-1}
\end{aligned}

Một "Cyclic convolution" - tích chập tuần hoàn hoặc positive wrapped convolution, PWC(x) được định nghĩa như sau:

$$
PWC(x)= \sum_{k=0}^{n-1}c_k \cdot x^k
$$

Với $c_k =\sum_{i=0}^{k}a_i \cdot b_{k-i} + \sum_{i=k+1}^{n-1}a_i \cdot b_{k+n-i}\mod q$. Nếu $C(x)$ là kết quả của tích chập trên trong vòng $\mathbb{Z}_q(x)$, nó cũng được định nghĩa như sau:

$$
PWC(x) = C(X) \mod{x^n - 1}
$$

ví dụ:

\begin{aligned}
A(x) &= 3x^2 + 2x + 4 \mod {x^4 -1 }\\
B(x) &= 4x^3 + 3x + 5 \mod {x^4 -1 }
\end{aligned}

\begin{array}{rrrrrrrr}
&&&& 3x^2 &+& 2x &+ 4 \\
&&&& 4x^3 &+& 3x &+ 5 \\
\hline
&&& 12x^5 &+& 8x^4 &+ 21x^3 &+ 22x^2 &+ 22x &+& 20\\
&&& 12x &+& 8 &+ 21x^3 &+ 22x^2 &+ 22x &+& 20 &\mod {x^4 -1 }\\
\hline
&&& 21x^3 &+& 22x^2 &+ 34x &+ 28 &\mod {x^4 -1 }\\
\end{array}

### Negacyclic Convolution

Cho 2 đa thức A(x) và B(x) có bậc là n-1 trong vành thương $\mathbb{Z}_q(x)/(x^n +1)$ với q số nguyên:

\begin{aligned}
A(x) &= a_0 + a_1 + \cdots a_{n-1}\cdot x^{n-1}\\
B(x) &= b_0 + b_1 + \cdots b_{n-1}\cdot x^{n-1}
\end{aligned}

Một negacyclic convolution hoặc negative wrapped convolution. NWC(x) được định nghĩa như sau:

$$
NWC(x)= \sum_{k=0}^{n-1}c_k \cdot x^k
$$

Với $c_k =\sum_{i=0}^{k}a_i \cdot b_{k-i} + \sum_{i=k+1}^{n-1}a_i \cdot b_{k+n-i}\mod q$. Nếu $C(x)$ là kết quả của tích chập trên trong vòng $\mathbb{Z}_q(x)$, nó cũng được định nghĩa như sau:

$$
NWC(x) = C(X) \mod{x^n + 1}
$$

ví dụ:

\begin{aligned}
A(x) &= 3x^2 + 2x + 4 \mod {x^4 +1 }\\
B(x) &= 4x^3 + 3x + 5 \mod {x^4 +1 }
\end{aligned}

\begin{array}{rrrrrrrr}
&&&& 3x^2 &+& 2x &+ 4 \\
&&&& 4x^3 &+& 3x &+ 5 \\
\hline
&&& 12x^5 &+& 8x^4 &+ 21x^3 &+ 22x^2 &+ 22x &+& 20\\
&&& -12x &+& -8 &+ 21x^3 &+ 22x^2 &+ 22x &+& 20 &\mod {x^4 + 1 }\\
\hline
&&& 21x^3 &+& 22x^2 &+ 10x &+ 20 &\mod {x^4 +1 }\\
\end{array}

### NTT-Based Convolutions

#### Primitive n-th Root of Unity
* nhắc lại:

Một primitive n-th root of uninty ( ta ký hiệu là $\alpha$) trong $\mathbb{Z}_q$ là:

\begin{array}{c}
\left\{
\begin{aligned}
\alpha ^ n & \equiv 1\\
\sum_{j=0} ^ {n-1} \alpha ^{j\cdot k} &\equiv 0\ \text{ for }1 \le k < n
\end{aligned}
\right.
\end{array}

#### NTT-Based Positive-Wrapped Convolution

##### Number Theoretic Transform based on $\alpha$

Phần này tức là chuyển vector hệ số $v = (v_0,\cdots , v_{n-1})$ sang $f = (f_0,\cdots , f_{n-1})$, mình đã giới thiệu ở phần DFT, ở đây mình sẽ kí hiệu lại phép ánh xạ này là:

$$
(v_0,\cdots,v_{n-1})\xrightarrow{NTT}(f_0,\cdots,f_{n-1})\\
$$

##### Inverse Number Theoretic Transform based on $\alpha$

Như phần trên mình ký hiệu lại INTT từ IDFT là:

$$
(f_0,\cdots,f_{n-1})\xrightarrow{INTT} (v_0,\cdots,v_{n-1})\\
$$

##### Using NTT to Calculate Positive-Wrapped Convolutions

Bởi vì NTT là một dạng của DFT trong vành đa thức. Nên ta có thể ứng dụng DFT's convolution theorem để tính positive-wrapped convolution": cho a,b là các vector hệ số của đa thức. The positive-wrapped convolution của a,b được tính là:

$$
c = INTT(NTT(a)\bullet NTT(b))
$$

với $\bullet$ là phép tính nhân trên $\mathbb{Z}_q$.

#### NTT-based Negative-Wrapped Convolution

Trong phần này mình sẽ giới thiệu Định nghĩa NTT và INTT trên cơ sở 2n-th root of unity, $ζ$, làm thế nào để sử dụng chúng để tính negative-wrapped hoặc negacyclic convolution.

##### Primitive 2n-th Root of Unity
Để tính toán được negative-wrapped convolution, chúng ta cần the primitive 2n-th root of unity, $ζ$.

Với $\mathbb{Z}_q$ là vành nguyên modulo q, và n-1 là bậc của đa thức $A(x)-B(x)$ và $\alpha$ là primitive n-th root of unity. Chúng ta định nghĩa $ζ$ là the primitive 2n-th root of unity khi và chỉ khi:

\begin{array}{c}
\left\{
\begin{aligned}
ζ^2 &\equiv \alpha &\mod{q}\\
ζ^\ &\equiv -1 &\mod{q}
\end{aligned}
\right.
\end{array}

##### Number Theoretic Transform Based on ζ
The negative - wrapped number theoretic transform ($NTT^ζ$) của một vector hệ số đa thức $f=NTT^ζ(v)$, ta có:

$$
f_k = \sum_{j=0} ^ {n-1} v_j \cdot \alpha ^{j\cdot k} \cdot ζ^j \mod {q}
$$

với $k=0,\cdots, n-1$, vì $ζ^2 \equiv \alpha \mod{q}$, chúng ta thay vào biểu thức trên:

$$
f_k = \sum_{j=0} ^ {n-1} v_j \cdot ζ^{2jk + j} \mod {q}
$$

##### Inverse Number Theoretic Transform Based on ζ

The negative-wrapped inverse of number theoretic transform (INTT) của một NTT vector $f$ là $v = INTT^{ζ^{-1}}(f)$, ta có:

$$
v_j = \frac{1}{n}\cdot \sum_{k=0} ^ {n-1}f_{k}\cdot \alpha ^{-j\cdot k} \cdot ζ^{-k} \mod {q}
$$

với $j = 0,\cdots,n-1$, tương tự ta có biểu thức:

$$
v_j = \frac{1}{n}\cdot \sum_{k=0} ^ {n-1}f_{k}\cdot ζ^{-(2jk+k)} \mod {q}
$$

##### Using NTT^ζ to Calculate Negative-Wrapped Convolutions
Tương tự với positive-wrapped thì ta có thể tính the negative-wrapped convolutions:

Với a,b là các vector hệ số đa thức,the negative-wrapped convolution của a, b - c được tính:

$$
c = INTT^{ζ^{-1}}(NTT^{ζ}(a)\bullet NTT^{ζ}(b))
$$

#### Cách chọn một modulus

Ta phải chọn một modulus-q thỏa các điều kiện như sau:
- Tồn tại the n-th root $\alpha$ trong $\mathbb{Z}_q$. Vì khi và chỉ khi có the n-th root $\alpha$ thì có mới sử dụng NTT để thực hiện đực positive-wrapped convolutions.
- Và phải tồn tại the 2n-th root $ζ$ để thực hiện negative-wrapped convolutions.

Nếu q là số nguyên tố, thì n phải là ước của p-1. Nếu q là tổ hợp:

$$
q = q_1 ^ {m_1}\cdot q_2 ^ {m_2}\cdots q_k ^ {m_k}
$$

n sẽ phải là ước của the greatest common divisor (GCD)của $(q_1-1,q_2-2,\cdots,q_k -1)$

Trong sơ đồ được đề suất cho NIST-PQC competition, những giá trị n và q được chuẩn hóa, bảng tóm tắt cho các giá trị.

:::info
- PWC-NTT friendly modulus q: được định nghĩa là nếu và chỉ nếu tồn tại n-th root of unity $\alpha$ trong $\mathbb{Z}_q$.
- NWC-NTT friendly modulus q: được định nghĩa là nếu và chỉ nếu tồn tại 2n-th root of unity $ζ$ trong $\mathbb{Z}_q$.
:::

Để phù hợp cho việc tối ưu thuật toán, thì n thường được chọn là lũy thừa của 2, và q được chọn theo công thức: $q \equiv 1 \mod{2n}$, thì lúc này ta sẽ có đầy đủ cách n-th root of unity, 2n-th root of unity:

$$
x^n+1=(x-ζ)\cdot (x-ζ^3)\cdots (x-ζ^{2n-1})\mod q
$$

### Fast NTT: An Adaptation of Fast-Fourier Transform to the Number Theoretic Transform

Trong các phần trước, các trình bày về NTT và INTT transformation vẫn có độ phức tạp khá lớn $O(n^2)$, vì vậy không có sự khác biiejt giữa phương pháp truyền thống của negacyclic convolution. Tuy nhiên vì NTT là một phần đặc biệt của DFT nên optimize trên DFT vẫn có thể được áp dụng vào NTT. Một kĩ thuật tối ưu kinh điển là Fast-Fourier Transform (FFT) được đề xuất bời Cooley-Tukey và Gentleman-Sande. Cả hai đều sử dụng butterflies divide và conquer technique để giảm độ phức tạp còn $O(n\log n)$.

Để giảm độ phức tạp được như thế ta sử dụng "devide và conquer" techniques bằng cách sử dụng tính chất tuần hoàn-periodicity và đối xứng-symmetry của $ζ$:
- Tuần hoàn: $ζ^ {k+2\cdot n} = ζ^k$.
- Đối xứng : $ζ^{k+n} = -ζ^k$.

Với k là số nguyên không âm. Phép tính n điểm NTT và INTT có thể chia làm làm n/2 điểm. Tuy, tuy nhiên kĩ thuật chia này có đôi phần khó.

#### Cooley-Tukey (CT) Algorithm for Fast-NTT

Từ việc tính $NTT^{^-1}$ trên 1 giá trị ta có thể chia làm 2 phần:

\begin{aligned}
f_k &= \sum_{j=0} ^ {n-1} v_j \cdot ζ^{2jk + j} \mod {q}\\
&= \sum_{j=0} ^ {n/2-1} v_{2j} \cdot ζ^{4jk + 2j} + \sum_{j=0} ^ {n/2-1} v_{2j+1} \cdot ζ^{4jk +2k + 2j +1} \mod{q}\\
&=\sum_{j=0} ^ {n/2-1} v_{2j} \cdot ζ^{4jk + 2j} + ζ^{2k+1} \sum_{j=0} ^ {n/2-1} v_{2j+1} \cdot ζ^{4jk + 2j } \mod{q}\\
\end{aligned}

Dựa trên tính chất đối xứng của ζ ta có :

$$
f_{k+n/2} = \sum_{j=0} ^ {n/2-1} v_{2j} \cdot ζ^{4jk + 2j} - ζ^{2k+1} \sum_{j=0} ^ {n/2-1} v_{2j+1} \cdot ζ^{4jk + 2j } \mod{q}\
$$

Đặt $A_k = \sum_{j=0} ^ {n/2-1} v_{2j} \cdot ζ^{4jk + 2j}$, $B = \sum_{j=0} ^ {n/2-1} v_{2j+1} \cdot ζ^{4jk + 2j }$, Nên ta có:

\begin{aligned}
f_k &=A_k + ζ^{2k+1}\cdot B \mod{q}\\
f_{k+n/2} &= A_k - ζ^{2k+1}\cdot B \mod{q}\\
\end{aligned}

Lưu ý: các giá trị $A_k$ , $B_K$ có thể được tính bằng n/2 điểm NTT. Nếu n là power of 2, quá trình này có thể lặp lại cho tất cả các hệ số. Hình dưới đầy mô tả quá trình trực quan của biểu thức, thường được gọi là CT butterfly:


Note: $ψ = ζ$

Ý tưởng là tính toán các số hạng tương tương tự ( như $A_k,B_K$ ) một lần rồi phân phối kết quả thay vì tính toán nhiều lần:

Sô giai đoạn cần thiết cho giai đoàn này cần là $\log_2(n)$.

#### Gentlema-Sande (GS) Algorithm for Fast-INTT

Với INTT, thay vì chia tổng của nó thông qua chỉ số chẵn lẻ, nó được tách bằng nữa trên nửa dưới của phép cộng:

\begin{aligned}
v_j
&= \frac{1}{n}
\left[
\sum_{k=0}^{\frac{n}{2}-1} f_k\,\zeta^{-(2j+1)k}
+
\sum_{k=0}^{\frac{n}{2}-1} f_{k+\frac{n}{2}}\,
\zeta^{-(2j+1)\left(k+\frac{n}{2}\right)}
\right] \\[6pt]
&= \frac{1}{n}
\left[
\sum_{k=0}^{\frac{n}{2}-1} f_k\,\zeta^{-(2j+1)k}
+
\zeta^{-(2j+1)\frac{n}{2}}
\sum_{k=0}^{\frac{n}{2}-1} f_{k+\frac{n}{2}}\,
\zeta^{-(2j+1)k}
\right] \\[6pt]
&= \frac{1}{n}
\left[
\sum_{k=0}^{\frac{n}{2}-1} f_k\,\zeta^{-(2j+1)k}
-
\sum_{k=0}^{\frac{n}{2}-1} f_{k+\frac{n}{2}}\,
\zeta^{-(2j+1)k}
\right].
\end{aligned}

Dựa trên tính chất tuần hoàn và đối xứng $ζ^{-1}$, đối với số hạng chẵn ta có:

\begin{aligned}
v_{2j} &=\frac{1}{n}\cdot ζ^{-2j} \cdot \sum_{k=0}^{\frac{n}{2}-1} \left[
\,f_k+
f_{\left(k+\frac{n}{2}\right)}
\right]\cdot ζ^{-4jk} \mod {q}\\
\end{aligned}

Tương tự cho các hệ số lẻ:

\begin{aligned}
v_{2j} &=\frac{1}{n}\cdot ζ^{-2j} \cdot \sum_{k=0}^{\frac{n}{2}-1} \left[
\,f_k-
f_{\left(k+\frac{n}{2}\right)}
\right]\cdot ζ^{-4jk} \mod {q}\\
\end{aligned}

đặt $A_j = \sum_{k=0}^{\frac{n}{2}-1} ζ^{-4jk}\,f_k$ và $B_j = \sum_{k=0}^{\frac{n}{2}-1} ζ^{-4jk}\,f_{k+n/2}$, nên ta có:

\begin{aligned}
v_{2j} &=\frac{1}{n}\cdot ζ^{-2j}(A_i + B_i) \mod {q}\\
v_{2j+1} &=\frac{1}{n}\cdot ζ^{-2j}(A_i - B_i) \mod {q}\\
\end{aligned}

Lưu ý: các giá trị $A_j,B_j$ có thể thu được dưới dạng n/2 điểm INTT. Nếu n là power of 2, quá trình này có được lặp lại. Phương trình này thường được gọi là GS butterfly.

Ý tưởng là tính toán các số hạng tương tương tự ( như $A_j,B_j$ ) một lần rồi phân phối kết quả thay vì tính toán nhiều lần:


#### Tổng hợp
Một các nhìn tổng quát cho biểu thức:

$$
c = INTT^{ζ^{-1}}(NTT^{ζ}(a)\bullet NTT^{ζ}(b))
$$

- $NTT^\zeta$ có tối ưu nên phần này có độ phức tạp là O($n \log n$) (cần (n/2)$\log_2(n)$ phép nhân và$ $n\log_2(n)$ phép cộng), Tương tự với $INTT^{ζ^{-1}}$.
- Phép Nhân trong NTT được coi là $O(n)$ vì chỉ là nhân các hệ số.

Từ đây ta có thể tính tổng quát Độ Phức tạp := $O(n) + 3 O(n\log n)$ = $O(n\log n)$.

## References

1. https://eprint.iacr.org/2024/585.pdf
2. https://dunglq2000.github.io/mathematics/discrete-mathematics/discrete-fourier-transform.html
3. https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
4. https://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt
5. v...v.v...