#prime-field #field #ntt #goldilocks

goldilocks-ntt

A library for fast NTTs over the Goldilocks prime field

1 unstable release

0.1.0 Dec 19, 2022

#744 in Math

MIT license

56KB
1.5K SLoC

Rust 1K SLoC // 0.1% comments WebGPU Shader Language 153 SLoC // 0.2% comments

Goldilocks NTT

Fast number theoretic transforms over the 64-bit Goldilocks prime field $\mathbb{F}_p$ with

$$ p = 2^{63} - 2^{32} + 1 $$

To do

Build run test bench

cargo fmt &&\
cargo clippy --all-features --all-targets &&\
cargo test --workspace --all-features --doc -- --nocapture &&\
cargo test --workspace --all-features --all-targets -- --nocapture &&\
cargo doc --workspace --all-features --no-deps
cargo test --all-features -- --test-threads 1 --nocapture

Run Criterion benchmarks

cargo bench --all-features --bench criterion --package goldilocks-ntt

cargo bench --all-features --bench criterion --package goldilocks-pcs

Create a baseline

cargo bench --all-features --bench criterion -- --save-baseline main
cargo bench --all-features --bench criterion -- --baseline-lenient main

Run NTT benchmarks

cargo bench --all-features --bench ntt -- ntt 32

Check documentation coverage

RUSTDOCFLAGS="-Z unstable-options --show-coverage"  cargo doc --workspace --all-features --no-deps
cargo +stable run --bin codegen > small.rs && mv small.rs src/ntt && cargo +stable test ntt::small

Inspect assembly using cargo-show-asm

cargo asm --lib -p goldilocks-ntt "ntt::small::ntt_2" 0
RUSTFLAGS="-Awarnings" cargo asm --lib --all-features -p goldilocks-ntt --rust "field::algo::generic::mul_redc_2"

See also

http://fftw.org/fftw-paper-ieee.pdf

https://netlib.org/utk/people/JackDongarra/CCDSC-2014/talk35.pdf

https://users.ece.cmu.edu/~franzf/papers/fft-enc11.pdf

https://github.com/ejmahler/RustFFT

https://gitlab.com/hatsya/open-source/cpads/-/blob/master/include/cpads/algebra/ff64.hpp

https://github.com/mir-protocol/plonky2/issues/1

https://github.com/mir-protocol/plonky2/issues/8

Dependencies

~180KB