Описание тега ntt

Number Theoretic Transform

• it is a form of discrete Fourier transform on finite fields
• has the same properties and usage as DFT
• mostly used for polynomial convolution
• and fast bigint multiplications like Schönhage-Strassen multiplication
• it is computed on integers so no rounding error occurs
• but it can overflow if too big numbers or dataset is used in comparison to modulo prime