Skip to content

The Pre-Requisite / Assumed-Known Maths 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

There are two versions of the pre-requisites: * The "Normal" pre-req's if you just want to understand the implementations and want to tweak it, fix some bugs, or make a new implementation based on a pre-existing one * The "Hardcore" pre-req's if you plan on trying to come up with your own algorithms, find "cheats" to make the algorithms faster, you want to find new use cases for the NTT / understand the details of the use cases, or if you are just really interested. Note: Do not waste your time on these materials unless you are really sure you want to and/or have good reason

Normal Pre-Requisites

A good enough grasp of the concepts involved in the following should hopefully be enough

  • Linear Algebra - Focusing on Finite Fields and understanding ideas like Vector Fields, Matrix Operations, etc
  • Abstract Algebra - Again focusing on Finite Fields, a very basic idea of things like Galois Theory, Algebraic Geometry, Coding Theory, etc
  • Simple Number Theory - Mostly just an understanding of Modular Arithmetic, Integer Fields, Prime Numbers, Operations on and with Polynomials, etc
  • Complex Analysis and by extension Fourier Analysis - The NTT is a special case of the Fast Fourier Transform

Hardcore Pre-Requisites

If you want to go into the maths surrounding the NTT, look at use cases such as PQC, ECC, and/or HE in more detail, or you're just a crazy mfer like me (andrew) and want to know things; you can bet that you will need to have studied the following topics (note this is very similar to the simple requirements but with way more detail in certain places):

  • An introduction to algebra which would be taught to mathematician's in undergraduate. I recommend:
  • Some kind of introduction to Number Theory, I recommend:
  • PLACEHOLDER
  • A good grasp of Group theory is going to be very helpful to you, I can recommend the following:
  • PLACEHOLDER