Introduction to the Already Discovered Algorithms for the NTT
WORK IN PROGRESS -- The SAL NTT Project and this part of the project by extension is not verified fully yet; use caution, and your brain
This is a WORK IN PROGRESS please be careful to read and think before you do anything. In addition if you find a problem let us know and we can try to find a fix. If you want to be really kind to us poor lads, fix it yourselves and let us know what we need to add to the docs to help other users/readers
If you already have a grasp of the maths/theory basics here then the quick coverage below should be enough and/or you may peruse some wikipedia articles on the following as reminders:
- A Complete Beginner Guide to the Number Theoretic Transform (NTT)
- A note on the implementation of the Number Theoretic Transform
- Numerical Recipes 3rd Edition: The Art of Scientific Computing Chapter 12!!!
- An Extensive Study of Flexible Design Methods for the Number Theoretic Transform
- Github link for previous paper: Parametric NTT/INTT Hardware
- A Flexible NTT-Based Multiplier for Post-Quantum Cryptography.
- Kind of an alt-link to the previous one: Designing Efficient and Flexible NTT Accelerators
- Designing Efficient and Flexible NTT Accelerators, Ahmet MALAL
- Key paper required for previous one: Design of a Flexible Schönhage-Strassen FFT Polynomial Multiplier with High-Level Synthesis to Accelerate HE in the Cloud
- A Flexible and Scalable NTT Hardware: Applications from Homomorphically Encrypted Deep Learning to Post-Quantum Cryptography Alt link