ecfft

Crates.ioecfft
lib.rsecfft
version0.1.0
sourcesrc
created_at2023-06-18 01:47:40.306367
updated_at2023-06-18 01:47:40.306367
descriptionElliptic curve fast fourier transform for all prime fields
homepage
repositoryhttps://github.com/andrewmilson/ecfft
max_upload_size
id893203
size129,658
Andrew Milson (andrewmilson)

documentation

README

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

Commit count: 40

cargo fmt