Function twenty_first::shared_math::ntt::ntt

pub fn ntt<FF: FiniteField + MulAssign<BFieldElement>>(
    x: &mut [FF],
    omega: BFieldElement,
    log_2_of_n: u32
)

Perform NTT on slices of prime-field elements

NTTs are Number Theoretic Transforms, which are Discrete Fourier Transforms (DFTs) over finite fields. This implementation specifically aims at being used to compute polynomial multiplication over finite fields. NTT reduces the complexity of such multiplication.

For a brief introduction to the math, see:

• https://cgyurgyik.github.io/posts/2021/04/brief-introduction-to-ntt/
• https://www.nayuki.io/page/number-theoretic-transform-integer-dft

The implementation is adapted from:

Speeding up the Number Theoretic Transform
for Faster Ideal Lattice-Based Cryptography
Longa and Naehrig

as well as inspired by https://github.com/dusk-network/plonk

• x - a mutable slice of prime-field elements of length n
• omega - a primitive nth root of unity
• log_2_of_n - a precomputation of log2(n) to avoid repeating its computation

A primitive nth root of unity means:

• omega^n = 1 (making it an nth root of unity), and
• omega^k ≠ 1 for all integers 1 ≤ k < n (making it a primitive nth root of unity)

This transform is performed in-place.