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

• Optimize transpose.
• Optimize twiddles in Cooley-Tukey.
• Good-Thomas inmplementation.
• Winograd NTT?

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

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 run --bin codegen > small.rs && mv small.rs src/ntt && cargo 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

• [plonky2]
• winterfell
• risc0

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

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