Module risc0_zkp::core::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.