Module scuttlebutt::field::fft

Various number theoretic utility functions used in the library.

Note: This library was adapted from https://github.com/snipsco/rust-threshold-secret-sharing

Traits

• FieldForFFT
  This trait indicates that a finite field is suitable for use in radix-N FFT. This means that it must have a power-of-N root of unity for any desired FFT size, i.e., a field element r_p, such that r_p^(N^p) = 1, for a size-3^p FFT. The PHI_EXP constant is the exponent of the largest FFT size supported, and root should return the N^pth root of unity.

Functions

• fft2
  Compute the 2-radix FFT of a_coef in the Zp field defined by prime.
• fft2_in_place
  Compute the in-place 2-radix FFT of a_coef in the Zp field defined by prime.
• fft2_inverse
  Inverse FFT for fft2.
• fft2_inverse_in_place
  Inverse FFT for fft2_in_place.
• fft3
  Compute the 3-radix FFT of a_coef in the Zp field defined by prime.
• fft3_in_place
  Compute the 3-radix FFT of a_coef in the Zp field defined by prime.
• fft3_inverse
  Inverse FFT for fft3.
• fft3_inverse_in_place
  Inverse FFT for fft3.
• lagrange_interpolation_at_zero
  Performs a Lagrange interpolation at the origin for a polynomial defined by points and values.