Difference between FFT and NTT

Question

What are the main differences between the Fast Fourier Transform (FFT) and the Number Theoretical Transform (NTT)?

Why do we use the NTT and not the FFT in cryptographic applications?

Which one is a generalization of the other?

Answer 1

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.

Answer 2

Disclaimer: Comp-Sci math ahead, proper mathematicians beware. ;)

Fast Fourier Transform (FFT) and Discrete Fourier Transform (DFT)

The FFT is an algorithm which allows to calculate the DFT, as well as its inverse, for complex-valued signals.

That is: Given a complex-valued signal $x = (x_0, \ldots, x_{n-1})$ of length $n$, the FFT allows the calculation of its $\operatorname{DFT}(x) = (X_0, \ldots, X_{n-1})$, the components of which are defined as: $$ X_l = \sum_{j = 0}^{n-1} x_j g^{-jl} $$ Where $g$ is a primitive $n$-th root of unity in the complex field, e.g. $e^{i 2 \pi / n}$.

Issues when working in the complex field

In computer science there are, however, downsides to working in the field of complex numbers. Namely:

• We need to worry about rounding issues
• Operations on floating-point numbers tend to be less performant than on integer numbers

Generalizing to other algebraic structures with the Number-theoretical transform (NTT)

However it turns out that the definition of the DFT is also meaningful over algebraic structures other than the complex field, as long as appropriate roots of unity can be found.

The NTT then refers to this 'conversion' of the problem to another structure, specifically to performing the DFT over a finite field - usually the finite field $F_p$ of integers modulo a prime $p$.

Advantages of working in a finite field

Working in a finite field means that:

• We need not worry about rounding
• Integer operations tend to be performant
• Certain integer operations (e.g. multiplications by powers of two) can be made even more performant

Which is why, in computer science, we tend to use a NTT to work over a finite field, rather than over the complex field.

Summary

To come back to your questions:

• In computer science we tend to use an NTT rather than FFT over the complex field as it is more practical and performant
• In some sense you could consider the generic-ring-DFT a generalization of complex-field-DFT (calculated via FFT) to other algebraic structures. Then the NTT would be the application of this generic-ring-DFT to finite fields. I do not know whether I'd call an NTT itself a generalization of the FFT though.

Reading

The above is heavily based on Crandall & Pomerance's "Prime Numbers: A Computational Perspective" (978-0387252827), which has been the majority of my exposure to the subject. There are also Wikipedia articles on the DFT over the complex field, its generalization to arbitrary rings, the later of which has a section on the NTT allowing to apply it to a finite field