INTT Algorithm by Hand

As seen in the previous article, the Inverse Number Theoretic Transform (INTT) is performed using a Vandermonde matrix, just like the NTT. This shows that both evaluation via the NTT and interpolation via the INTT are similar operations.

The problem with directly using the Vandermonde matrix for evaluation or interpolation is that multiplying a $k \times k$ matrix by a vector takes $\mathcal{O}(k^2)$ time. Fortunately, when using the $k$-th roots of unity, with $k$ a power of 2, a fast method that does not rely on matrix multiplication can be used, reducing the time complexity to $\mathcal{O}(k \log k)$.

The fast method for the NTT was introduced in the chapter “NTT Algorithm by Hand.” In this chapter, we study the fast method for the INTT.

The idea is simple: to interpret polynomial interpolation as an evaluation, allowing the use of the same method employed for the NTT.

Evaluation and Interpolation

As a recap, the NTT allows us to transform a polynomial of degree at most $k-1$ from its coefficient form,

to its point-value form,

by evaluating the polynomial at the $k$-th roots of unity. This is called evaluation.

Interpolation is the opposite of evaluation: it is the process of transforming a polynomial from its point-value form to its coefficient form.

Interpolation as evaluation

Evaluations and interpolations at the $k$-th roots of unity are similar operations because both are performed using a Vandermonde matrix.

For better visualization, consider a polynomial of degree at most 3,

evaluated at the $4$-th roots of unity

The evaluation can be written as

The interpolation can be written as

Inspired by the evaluation structure, we can view $\frac{f(1)}{4}, \frac{f(\omega)}{4}, \frac{f(\omega^2)}{4}$ and $\frac{f(\omega^3)}{4}$ as the coefficients of a new polynomial $\tilde{f}(x)$, defined as

In this terms, the coefficients $a,b,c$ and $d$ are the evaluations of $\tilde{f}(x)$ at the following points:

Therefore, we can interpret interpolation as the evaluation of another polynomial. The crucial observation is that the inverse NTT does not require a fundamentally different algorithm.

Once the point-value representation is reinterpreted as the coefficient vector of a new polynomial, interpolation becomes an evaluation at a permuted set of roots of unity. In this sense, evaluation and interpolation are the same operation.

Avoiding working with inverses of the roots of unity

As shown in the transformation

the interpolation involves evaluations at the inverses of the roots of unity. However, we can avoid working with inverses.

Consider $\omega^{-1}$. Among the $4$th roots of unity, it is the element that, when multiplied by $\omega$, gives 1. Since

we have $\omega^{-1} = \omega^3$.

Similarly,

Thus, the coefficients $a,b,c$ and $d$ are the evaluations of

at the following points:

Using the fact that $\omega^2 = -1$, we can rewrite these as

Doing the INTT by hand

A polynomial of degree at most $k-1$, where $k$ is a power of 2, can be evaluated at the $k$-th roots of unity using the fast method explained in the chapter NTT Algorithm by Hand.

The evaluations of

at the points $\tilde{f}(1), \tilde{f}(-1), \tilde{f}(\omega)$ and $\tilde{f}(-\omega)$ are illustrated below.

The idea is to group the even and odd powers as

and evaluate $\tilde{f}(x)$ at $\sqrt{\sqrt{1}}$. At each evaluation of an innermost square root, the expression branches into two, one for each value of the square root. This continues until no square roots remain, at which point the procedure ends.

We obtain

Let us confirm that this matches the result obtained from the Vandermonde matrix:

Using

we rewrite it as

This leads to

which are the same expressions obtained by the fast algorithm.

The key difference is that the fast algorithm runs in $\mathcal{O}(k \log k)$ time, whereas the direct matrix multiplication takes $\mathcal{O}(k^2)$ time.

Polynomials of degree $k-1$

What we did in the previous section for a polynomial of degree $3$ can be extended to polynomials of any degree.

Suppose we have a polynomial $f(x)$ evaluated at the $k$-th roots of unity, where $k$ is a power of $2$:

To recover the coefficients of the polynomial $f(x)$, of degree at most $k-1$, that passes through these points, we define a new polynomial $\tilde{f}(x)$ as

The coefficients of $f(x)$ are then given by

This article is part of a series on the Number Theoretic Transform in our ZK Book