Performance Analysis of NTT Algorithms

The Number Theoretic Transform is an important tool in Cryptography, as it can be used to multiply polynomials in the rings \(\displaystyle \mathbb {Z}_q[x]/\langle x^n-1 \rangle \) and \(\displaystyle \mathbb {Z}_q[x]/\langle x^n+1 \rangle \) . In its plain version, the NTT is slower than the direct multiplication method for these rings. To overcome this disadvantage, some optimised variants of the NTT have been proposed in recent years. This contribution analyses one of these variants and presents an empirical comparison of the running time for the three methods considered in the study, which allows to determine the length of the polynomials for which each method is the fastest.