Number Theoretic Transform
Presentation: https://youtu.be/jeHQtLduHN8
Preliminaries
Discrete Linear Convolution
Convolution is a mathematical operation that blends two functions (or signals) to produce a third function, which shows how one function modifies or overlaps with the other.
A convolution is linear if it satisfies the properties of additivity and homogeneity. This means that the convolution of a linear combination of sequences is the same as the corresponding linear combination of their convolutions. For example,
So discrete linear convolution is when it is working on sequences of integers rather than on continuous functions.
Polynomial Multiplication
Definition 1: Suppose that and are polynomials of degree in the ring where and is the polynomial variable, a polynomial multiplication of and is defined as:
where , and are the polynomial coefficients of and respectively.
Polynomial multiplication is equivalent to a discrete linear convolution between the coefficients' vectors and .
Cyclic Convolution
Definition 2: Suppose that and are polynomials of degree in the quotient ring where . A cyclic convolution or positive wrapped convolution (PWC) is defined as:
where . If from equation is the result of their linear convolution in the ring , it can also be defined as:
Naive method to calculate the is through a polynomial multiplication followed by a long division. This method has complexity.
The term "cyclic" stems from the fact that cycles back to in this quotient ring. For example, will map to in this quotient ring.
Negacyclic convolution
Definition 3: Suppose that and are polynomials of degree in the quotient ring where . A negacyclic convolution or negative wrapped convolution, is defined as:
where . If from equation is the result of their linear convolution in the ring , it also can be defined as:
Note that the only difference between cyclic and negacyclic convolution is the divisor.
The term "negacyclic" stems from the fact that cycles back to in this quotient ring. For example, will map to in this quotient ring.
Number Theoretic Transform
Many researchers do not differentiate the term NTT and FFT-based algorithms to calculate NTT, which creates confusion when understanding the topic. This report refers to the transformation itself as NTT and the FFT-like algorithms as fast-NTT
The classical NTT has quadratic complexity of while fast-NTT algorithms have a more efficient quasi-linear complexity
Remember that for NTT, we are particularly interested in the evaluations at the roots of the quotient polynomial. ( and we want the to vanish).
Definition 4: Let be an integer ring modulo , and is the polynomial degree of and . Such rings have a multiplicative identity (unity) of 1. Define as primitive -th root of unity in if and only if:
and
for all .
One thing to note is that the primitive -th root of unity in a ring might not be unique. For example, in a ring , primitive 3rd root of unity can be and . The choice of value of will be important in calculating and .
Definition 5: The Number Theoretic Transform (NTT) of a vector of polynomial coefficients is defined as , where:
and . Here, denotes the evaluations of the polynomial defined by over which are the roots of .
Definition 6: The Inverse of Number Theoretic Transform (INTT) of an NTT vector is defined as , where:
and .
Note that the INTT has a very similar formula to NTT. The only differences are replaced by its inverse in and a scaling factor. It always holds that .
In the ZK scene, it is common to work on a polynomial with some max degree . This just means that we are working on polynomials from the quotient ring . In such rings, we must utilize positive-wrapped convolution.
In the context of PQC and HE, the chosen ring is mostly instead of . One must calculate the polynomial multiplications via the negative-wrapped convolution in such rings. To calculate negative-wrapped convolution, one needs the primitive -th root of unity, .
Definition 7: Let be an integer ring modulo , and is the polynomial degree of and and is its primitive -th root of unity. Define as the primitive -th root of unity if and only if:
Example. In a ring and , when , the value of can be 1925 or 5756 as and . Therefore, one can choose the value of or .
Definition 8: The Negative-Wrapped Number Theoretic Transform () of a vector of polynomial coefficients is defined as , where:
and . Here, denotes the evaluations of the polynomial defined by over which are the roots of .
Definition 9: The Negative-Wrapped Inverse of Number Theoretic Transform (INTT) of an NTT vector is defined as , where:
and . Substituting yields:
To reduce the complexity and fasten the process of the matrix multiplication needed for the NTT transformation, one can use ‘‘divide and conquer’’ techniques by utilizing the periodicity and symmetry property of:
Cooley-Tukey (CT) Algorithm for Fast NTT
PWC case
From equation (8) for , one can separate the summation into two parts, based on odd and even indices:
Similarly, we can get the equation for by using the fact that :
If we denote, and , the equation and becomes:
With this finding, we can calculate and for and calculate by reusing them for the upper half. Notice that and can be calculated using point NTT so if we repeat recursively, we can achieve the best case scenario which occurs when is a power of 2.
Example. Let's consider the case when .
The idea is to calculate similar terms in the brackets once and then distribute the results instead of calculating them multiple times.
NWC case
From equation for , one can separate the summation into two parts similarly into following:
Based on the 's symmetry properties:
Let and , equations and become:
With this finding, we can calculate and for and calculate by reusing them for the upper half. Notice that and can be calculated using point NTT so if we repeat recursively, we can achieve the best case scenario which occurs when is a power of 2.

Figure 1 illustrates how this butterfly operation is denoted as a graph. This figure represents the computation of and .
Gentleman-Sande (GS) Algorithm for Fast INTT
PWC case
For the INTT, instead of dividing the summation by even and odd indices, it is separated by the lower and upper half of the summation. From equation for and ignoring term:
If we consider the odd and even term separately, we get:
Let and , equation and become:
With this finding, we just need to calculate and for . Notice that and can be calculated using point INTT so if we repeat recursively, we can achieve the best case scenario which occurs when is a power of 2.
NWC case
Similarly, continuing from equation for , ignoring term, we got:
If we consider the odd and even term, we get:
Let and , then equation and becomes:
With this finding, we just need to calculate and for . Notice that and can be calculated using point INTT so if we repeat recursively, we can achieve the best case scenario which occurs when is a power of 2.

Figure 2 illustrates how this butterfly operation is denoted as a graph. This figure represents the computation of and .
References:
Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations by A. Satriawan et al (2023)
Lifting a butterfly – A component-based FFT by Sibylle Schupp (2003)
Written by BATZORIG ZORIGOO of A41
Last updated