Module ntt 

An implementation of a number-theoretic transform (NTT).

Functions

bit_rev_32

Reverses the bits in a 32-bit number.

bit_reverse

Bit-reverses the indices in an array of (1 << n) numbers. This permutes the values in the array so that a value which is previously in index i will now go in the index i’, given by reversing the bits of i.

evaluate_ntt

Perform a forward butterfly transform of a buffer of (1 << n) numbers.

expand

Expand the input into output to support polynomial evaluation on input.len() * (1 << expand_bits) points.

interpolate_ntt

Perform a reverse butterfly transform of a buffer of (1 << n) numbers. The result of this computation is a discrete Fourier transform, but with changed indices. This is described here. The output of rev_butterfly(io, n) at index i is the sum over k from 0 to 2^n-1 of io[k] ROU_REV[n]^(k i’), where i’ is i bit-reversed as an n-bit number and ROU_REV are the ‘reverse’ roots of unity.