# Resources

## Useful Repos
- **Ministark**: GPU accelerated STARK prover built on arkworks-rs https://github.com/andrewmilson/ministark
- **Winterfell**: A STARK prover and verifier for arbitrary computations https://github.com/facebook/winterfell
- **GPUSnarks**: CUDA implementation of Fast Fourier Transformations on finite fields https://github.com/MariusVanDerWijden/gpusnarks

## Useful Links

- **CUDA Introduction**: https://www.notamonadtutorial.com/cuda-from-scratch/
- **Rust CUDA ecosystem**: https://github.com/Rust-GPU/Rust-CUDA
- **Reed-Solomon Explained**: https://www.youtube.com/watch?v=1pQJkt7-R4Q

### FFT / NTT
- **FFT Explained**: https://www.youtube.com/watch?v=h7apO7q16V0
- **Cooley-Tukey FFT Algorithm** https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
- **DFT over a ring**: https://en.wikipedia.org/wiki/Discrete_Fourier_transform_over_a_ring#Number-theoretic_transform
- **Brief introduction to NTT**: https://cgyurgyik.github.io/posts/2021/04/brief-introduction-to-ntt/
- **(primitive) roots of unity of a finite field** https://www.youtube.com/watch?v=hNuz3AHbRRg
- **FFT and Interpolation implemented in Metal**: https://github.com/andrewmilson/ministark/tree/main/gpu-poly
- **Nayuki NTT**: abstract and demo of NTT https://www.nayuki.io/page/number-theoretic-transform-integer-dft (includes calculator)

### Butterfly, bit reversal, DIT and DIF, n-radix
- **Butterfly diagrams explained simply** https://www.alwayslearn.com/DFT%20and%20FFT%20Tutorial/DFTandFFT_FFT_TheButterflyDiagram.html
- **2-radix FFT explained** https://www.youtube.com/watch?v=lGCAlv3G8Oc
- **FFT stages interpreted through Linear Algebra** https://www.youtube.com/watch?v=A6eBcTHlEL4
- **Short and informal doc about parallel FFT** https://cs.wmich.edu/gupta/teaching/cs5260/5260Sp15web/studentProjects/tiba&hussein/03278999.pdf
- **Another explanation of 2-radix FFT, with mentions to other-radixes algorithms** https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#The_radix-2_DIT_case
- **Comprehensive book about FFT and its parallelization (super recommended)**: http://dsp-book.narod.ru/FFTBB/0270_PDF_TOC.pdf

### Finite Field implementations
risc0
- Tech: Metal & CUDA
- Felt size: U32
- Modulo: hardcoded

ministark
- Tech: Metal
- Felt size: felt U64, U128, U256
- Modulo: hardcoded

gpusnarks
- Tech: CUDA
- Size: usa
- Modulo: hardcoded

Z-Price MSM
- Tech: CUDA