ntt.md

NTTnumber theoretic transform
cyber mathematics cryptography entity cyber
π 0.01%

Number Theoretic Transform: a discrete Fourier transform over a finite field, enabling fast polynomial multiplication in stark proof systems over the goldilocks field

NTT replaces complex roots of unity with primitive roots in a prime field, achieving O(n log n) polynomial multiplication with exact integer arithmetic

in cyber, NTT is a core operation in STARK proof generation, where large polynomial evaluations and interpolations dominate computation cost

efficient NTT implementations exploit the structure of Mersenne primes and goldilocks field primes to maximize hardware parallelism

Dimensions

jali/specs/ntt
ntt — negacyclic number theoretic transform the NTT converts between coefficient form and evaluation form in R_q = F_p[x]/(x^n+1). multiplication in evaluation form is pointwise — n independent F_p multiplications instead of O(n²) convolution. the problem naive polynomial multiplication in R_q…
nebu/specs/ntt
NTT specification the Number Theoretic Transform over the Goldilocks field. the algebraic engine behind STARK proving, polynomial arithmetic, and TFHE operations in cyber. roots of unity the multiplicative group F_p* has order p − 1 = 2³² × (2³² − 1). the factor 2³² provides a principal 2³²-th root…

Linked References

Local Graph