ECFFT

This library enables fast polynomial arithmetic over any finite field by implementing all the algorithms outlined in Elliptic Curve Fast Fourier Transform (ECFFT) Part I:

Algorithm	Description	Runtime
ENTER	Coefficients to evaluations (fft analogue)	$\mathcal{O}(n\log^2{n})$
EXIT	Evaluations to coefficients (ifft analogue)	$\mathcal{O}(n\log^2{n})$
DEGREE	Computes a polynomial's degree	$\mathcal{O}(n\log{n})$
EXTEND	Extends evaluations from one set to another	$\mathcal{O}(n\log{n})$
MEXTEND	EXTEND for special monic polynomials	$\mathcal{O}(n\log{n})$
MOD	Calculates the remainder of polynomial division	$\mathcal{O}(n\log{n})$
REDC	Computes polynomial analogue of Montgomery's REDC	$\mathcal{O}(n\log{n})$
VANISH	Generates a vanishing polynomial (from section 7.1)	$\mathcal{O}(n\log^2{n})$

There are also some relevant algorithms implemented from ECFFT Part II:

Algorithm	Description	Runtime
FIND_CURVE	Finds a curve over $\mathbb{F}_q$ with a cyclic subgroup of order $2^k$	$\mathcal{O}(2^k\log{q})$

Build FFTrees at compile time

FFTrees are the core data structure that the ECFFT algorithms are built upon. FFTrees can be generated and serialized at compile time and then be deserialized and used at runtime. This can be preferable since generating FFTrees involves a significant amount of computation. While this approach improves runtime it will significantly blow up a binary's size. Generating a FFTree capable of evaluating/interpolating degree $n$ polynomials takes $\mathcal{O}(n\log^3{n})$ - the space complexity of this FFTree is $\mathcal{O}(n)$.

// build.rs

use ark_serialize::CanonicalSerialize;
use ecfft::{secp256k1::Fp, FftreeField};
use std::{env, fs::File, io, path::Path};

fn main() -> io::Result<()> {
    let fftree = Fp::build_fftree(1 << 16).unwrap();
    let out_dir = env::var_os("OUT_DIR").unwrap();
    let path = Path::new(&out_dir).join("fftree");
    fftree.serialize_compressed(File::create(path)?).unwrap();
    println!("cargo:rerun-if-changed=build.rs");
    Ok(())
}

// src/main.rs

use ark_ff::One;
use ark_serialize::CanonicalDeserialize;
use ecfft::{ecfft::FFTree, secp256k1::Fp};
use std::sync::OnceLock;

static FFTREE: OnceLock<FFTree<Fp>> = OnceLock::new();

fn get_fftree() -> &'static FFTree<Fp> {
    const BYTES: &[u8] = include_bytes!(concat!(env!("OUT_DIR"), "/fftree"));
    FFTREE.get_or_init(|| FFTree::deserialize_compressed(BYTES).unwrap())
}

fn main() {
    let fftree = get_fftree();
    // = x^65535 + x^65534 + ... + x + 1
    let poly = vec![Fp::one(); 1 << 16];
    let evals = fftree.enter(&poly);
    let coeffs = fftree.exit(&evals);
    assert_eq!(poly, coeffs);
}

References

• Elliptic Curve Fast Fourier Transform (ECFFT) Part I
• Elliptic Curve Fast Fourier Transform (ECFFT) Part II
• The ECFFT algorithm blogpost by wborgeaud