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.