Module fft

Traits

• CurveAffine
  This trait is the affine counterpart to Curve and is used for serialization, storage in memory, and inspection of $x$ and $y$ coordinates.
• CurveExt
  This trait is a common interface for dealing with elements of an elliptic curve group in a “projective” form, where that arithmetic is usually more efficient.
• 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