FFTNTT

FFTNTT, short for Fast Fourier Transform based Number Theoretic Transform, refers to a class of algorithms that compute the discrete Fourier transform over a finite field or ring using FFT-like techniques. In a NTT, the input sequence is transformed using a primitive n-th root of unity ω in a finite modulus p, with arithmetic performed modulo p. The FFTNTT adapts Cooley–Tukey or similar FFT decompositions to perform the transform in O(n log n) modular operations, typically when n is a power of two and n divides p−1. Moduli are often chosen as primes of the form p = c·2^k + 1 to provide large 2^k-th roots of unity, with 998244353 being a common example.

Key features include in-place computation, precomputation of twiddle factors (powers of ω), and the use of efficient modular multiplication (e.g., Montgomery or Barrett reduction) to keep intermediate values within word size. An inverse transform uses ω^{-1} and a division by n modulo p.

FFTNTTs are widely used for fast polynomial multiplication in digital signal processing, cryptography, and error-correcting codes, especially in lattice-based schemes and post-quantum cryptography where large degree polynomial convolutions are common. They enable convolution modulo p by transforming coefficient arrays, multiplying pointwise, and applying an inverse transform, all under modular arithmetic.

Limitations include the need for appropriate modulus and root of unity, which constrains n; for arbitrary lengths, Bluestein's algorithm or CRT-based multiple-modulus approaches may be employed. The technique is typically implemented in software libraries and hardware accelerators targeting high-performance modular arithmetic.