Skip to content

Cooley-Tukey

This is a well-known algorithm involving "butterfly" MACs and a pre-chosen radix value. Follows decimation-in-frequency FFT structure.

If we generally state our NTT function as the following:

NTT(x):=X(k)=i=0N1(xαik) mod P

With α:= radix, P:= field modulus

Then we can "rearrange" this as follows:

X(k)=[j=0N/(21)(x(2j)α(2j)k) mod P]+[j=0N/(21)(x(2j+1)α(2j+1)k) mod P]

Disclaimer

This page is just a general idea and basic overview of implementing the NTT, both in HW and in SW. If you need more details on the implementation(s) there is more detail in the various pages for the algorithms. If you need more information about the theory then there is of course more information found in the maths and theory, and pre-requisite maths pages.

  1. A Complete Beginner Guide to the Number Theoretic Transform (NTT)
  2. A note on the implementation of the Number Theoretic Transform
  3. An Extensive Study of Flexible Design Methods for the Number Theoretic Transform
  4. A Flexible NTT-Based Multiplier for Post-Quantum Cryptography.
  5. Designing Efficient and Flexible NTT Accelerators, Ahmet MALAL
  6. A Flexible and Scalable NTT Hardware : Applications from Homomorphically Encrypted Deep Learning to Post-Quantum Cryptography Alt link