Module fft

Source

Re-exports§

pub use crate::CurveAffine;
pub use crate::CurveExt;

Traits§

FftGroup
This represents an element of a group with basic operations that can be performed. This allows an FFT implementation (for example) to operate generically over either a field or elliptic curve group.

Functions§

best_fft
Performs a radix-$2$ Fast-Fourier Transformation (FFT) on a vector of size $n = 2^k$, when provided log_n = $k$ and an element of multiplicative order $n$ called omega ($\omega$). The result is that the vector a, when interpreted as the coefficients of a polynomial of degree $n - 1$, is transformed into the evaluations of this polynomial at each of the $n$ distinct powers of $\omega$. This transformation is invertible by providing $\omega^{-1}$ in place of $\omega$ and dividing each resulting field element by $n$.
recursive_butterfly_arithmetic
This perform recursive butterfly arithmetic