pub fn ntt<FF>(x: &mut [FF])Expand description
§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 https://eprint.iacr.org/2016/504.pdf
as well as inspired by https://github.com/dusk-network/plonk
The transform is performed in-place. If called on an empty array, returns an empty array.
For the inverse, see iNTT.
§Panics
Panics if the length of the input slice is
- not a power of two
- larger than
u32::MAX