TL;DR Bạn cần NTT để tính toán chính xác trong các ứng dụng tiền điện tử.
FFT chỉ là một thuật toán để đánh giá DFT truyền thống, đối với các vectơ có giá trị phức tạp (lưu ý số thực và số nguyên là tập con của trường phức nên nó cũng áp dụng cho chúng) $(f_0,\dots,f_{N-1})$ chiều dài $N$ được xác định trên trường phức $\mathbb{C}$ sử dụng gốc phức của sự thống nhất của trật tự $N.$
Ở đây chúng tôi có
$$
F(\lambda)=\sum_{k=0}^{N-1} f_k e^{2 \pi i \lambda k/N}=
\sum_{k=0}^{N-1} f_k \xi_N^{\lambda k}, \quad
\xi_N:=e^{2 \pi i /N}, \lambda=0,1,\ldots,N-1
$$
Một gốc rễ phức hợp như vậy của sự thống nhất tồn tại cho tất cả $N$, tuy nhiên FFT hiệu quả hơn nếu $N$ là hỗn hợp, hiệu quả cao nhất thu được cho $N=2^m,$ cho một số nguyên $m.$
Các vấn đề với DFT: Đối với mật mã, chúng tôi làm việc với các đối tượng hữu hạn và thực sự có thể đạt được độ chính xác đầy đủ, điều này không áp dụng được trong thực tế trong trường phức, vì lập luận về căn phức của đơn vị là không hợp lý và số học chính xác nói chung là không thể.
Bây giờ, của NTT, dù dựa trên trường hữu hạn hay nghiệm nguyên của phép đơn vị modulo các vành nhất định, cung cấp cho chúng tôi độ chính xác đầy đủ (các DFT phức tạp không thể làm điều này và không thể được sử dụng cho tiền điện tử) và được đánh giá trong vòng gốc được sử dụng trong mật mã. Chúng vẫn là DFT. Và đối với độ dài nhất định có thể có triển khai hiệu quả.
Chọn NTT:
Giả sử vectơ đầu vào là một chuỗi các $N$ số nguyên không âm.
Nói chung, người ta cần chọn một mô đun $M$ như vậy mà $1â¤N<M$ và mọi giá trị đầu vào đều nằm trong phạm vi $[0,M).$ Nếu chúng ta nói triển khai tiền điện tử, thì chúng ta đã biết mô-đun.
Chọn một số nguyên $kâ¥1$ và xác định $N'=kN+1$ như mô đun làm việc. Chúng tôi cần $N'â¥M,$ và để đơn giản lấy $N'$ thành số nguyên tố. Định lý Dirichlet đảm bảo rằng $N$ và $M,$ có thể chọn $k$ để làm cho $N'$ một số nguyên tố.
Bởi vì $N'$ là số nguyên tố, nhóm nhân của $\mathbb{Z}_{N'}$ có kích thước $Ï(N')=N'â1=kN$ cũng như máy phát điện $g,$ đó cũng là căn nguyên thủy thứ (N'â1) của đơn vị.
Để cho $\omegaâ¡g^k \pmod N'.$ sau đó $\omega$ là một nguyên thủy $N$gốc của sự thống nhất, theo yêu cầu để có được DFT có độ dài $N,$ vì vậy đây là NNT:
$$
F(\lambda)=\sum_{k=0}^{N-1} f_k \omega^{\lambda k},\quad \lambda \in \mathbb{Z}_N.
$$
Có thể áp dụng phép rút gọn Montgomery (hoặc phép rút gọn Barrett kém hiệu quả hơn) để tăng tốc số học mô-đun trong NTT.
