#prime #field #ntt #goldilocks

goldilocks-ntt

A library for fast NTTs over the Goldilocks prime field

1 unstable release

0.1.0 Dec 19, 2022

#346 in Math

MIT license

50KB
1K SLoC

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

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

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

Dependencies

~63KB