ECFFT

此库通过实现椭圆曲线快速傅里叶变换（ECFFT）第一部分中概述的所有算法，实现了在任何有限域上快速多项式算术。

还实现了来自ECFFT第二部分的一些相关算法

编译时构建FFTrees

FFTrees是ECFFT算法构建的核心数据结构。可以在编译时生成和序列化FFTrees，然后在运行时反序列化和使用。这可能是首选的，因为生成FFTrees涉及大量的计算。虽然这种方法提高了运行时间，但它将显著增加二进制文件的大小。生成一个能够评估/插值度数为$n$的多项式的FFTTree需要$\mathcal{O}(n\log^3{n})$ - 该FFTTree的空间复杂度为$\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);
}

参考文献

• 椭圆曲线快速傅里叶变换（ECFFT）第一部分
• 椭圆曲线快速傅里叶变换（ECFFT）第二部分
• ECFFT算法博客文章，作者wborgeaud