TL;DR Aveți nevoie de NTT-uri pentru aritmetica exactă în aplicațiile cripto.
FFT este doar un algoritm pentru evaluarea DFT tradițională, pentru vectori cu valori complexe (relele reale și întregi sunt subseturi ale câmpului complex, deci se aplică și acestora) $(f_0,\dots,f_{N-1})$ de lungime $N$ care este definită peste câmpul complex $\mathbb{C}$ folosind rădăcina complexă a unității de ordine $N.$
Aici, avem
$$
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
$$
O rădăcină atât de complexă a unității există pentru toți $N$, cu toate acestea, FFT este mai eficient dacă $N$ este compozit, cel mai mare randament fiind obtinut pentru $N=2^m,$ pentru un număr întreg $m.$
Probleme cu DFT: Pentru criptografie lucrăm cu obiecte finite și putem obține de fapt o precizie deplină care nu se aplică în practică în domeniul complex, deoarece argumentul rădăcinii complexe a unității este irațional și aritmetica exactă este imposibilă în general.
Acum, NTT-urile, indiferent dacă se bazează pe un câmp finit sau pe rădăcini întregi ale unității modulo anumite inele, dă-ne precizie deplină (DFT-urile complexe nu pot face acest lucru și nu pot fi utilizate pentru cripto) și sunt evaluate în inelul nativ care este utilizat în criptografie. Sunt încă DFT-uri. Și pentru anumite lungimi pot avea implementări eficiente.
Alegerea unui NTT:
Să presupunem că vectorul de intrare este o secvență de $N$ numere întregi nenegative.
În general, trebuie să alegeți un modul $M$ astfel încât $1â¤N<M$ și fiecare valoare de intrare este în interval $[0,M).$ Dacă spunem că implementăm cripto, știm deja modulul.
Selectați un număr întreg $kâ¥1$ și definiți $N'=kN+1$ ca modul de lucru. Avem nevoie $N'â¥M,$ iar pentru simplitate ia $N'$ să fie număr prim. Teorema lui Dirichlet garantează că dat $N$ și $M,$ Poți alege $k$ a face $N'$ un prim.
pentru că $N'$ este prim, grupul multiplicativ al $\mathbb{Z}_{N'}$ are dimensiune $Ï(N')=N'â1=kN$ precum și un generator $g,$ care este și o primitivă (N'â1)-a rădăcină a unității.
Lăsa $\omegaâ¡g^k \pmod N'.$ Atunci $\omega$ este un primitiv $N$a-a rădăcină a unității, așa cum este necesar pentru a obține o DFT de lungime $N,$ deci acesta este NNT:
$$
F(\lambda)=\sum_{k=0}^{N-1} f_k \omega^{\lambda k},\quad \lambda \in \mathbb{Z}_N.
$$
Este posibil să aplicați reduceri Montgomery (sau reduceri Barrett mai puțin eficiente) pentru a accelera aritmetica modulară într-un NTT.
