TL;DR You need NTTs for exact arithmetic in crypto applications.
FFT is just an algorithm for evaluating the traditional DFT, for complex valued (note reals and integers are subsets of the complex field so it applies to them as well) vectors $(f_0,\dots,f_{N-1})$ of length $N$ which is defined over the complex field $\mathbb{C}$ using the complex root of unity of order $N.$
Here, we have
$$
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
$$
Such a complex root of unity exists for all $N$, however the FFT is more efficient if $N$ is composite, the highest efficiency being obtained for $N=2^m,$ for some integer $m.$
Problems with DFT: For cryptography we work with finite objects, and can actually obtain full precision which does not apply in practice in the complex field, since the argument of the complex root of unity is irrational and exact arithmetic is impossible in general.
Now, the NTT's, whether based on a finite field or integer roots of unity modulo certain rings, give us full precision (complex DFTs cannot do this and can't be used for crypto), and are evaluated in the native ring that is used in cryptography. They are still DFTs. And for certain lengths can have efficient implementations.
Choosing an NTT:
Suppose the input vector is a sequence of $N$ non-negative integers.
In general one needs to choose a modulus $M$ such that $1≤N<M$ and every input value is in the range $[0,M).$ If we are say implementing crypto, we already know the modulus.
Select some integer $k≥1$ and define $N'=kN+1$ as the working modulus. We need $N'≥M,$ and for simplicity take $N'$ to be a prime number. Dirichlet’s theorem guarantees that given $N$ and $M,$ can choose $k$ to make $N'$ a prime.
Because $N'$ is prime, the multiplicative group of $\mathbb{Z}_{N'}$ has size $φ(N')=N'−1=kN$ as well as a generator $g,$ which is also a primitive (N'−1)th root of unity.
Let $\omega≡g^k \pmod N'.$ Then $\omega$ is a primitive $N$th root of unity, as required to obtain a DFT of length $N,$ so this is the NNT:
$$
F(\lambda)=\sum_{k=0}^{N-1} f_k \omega^{\lambda k},\quad \lambda \in \mathbb{Z}_N.
$$
It’s possible to apply Montgomery reductions (or the less efficient Barrett reductions) to speed up the modular arithmetic in an NTT.
