Computes the Inverse Number-Theoretic Transform (INTT) of $X$.

Parameters:¶

X: ArrayLike¶

The input sequence of integers $X$.

size: int | None = None¶

The size $N$ of the INTT transform, must be at least the length of $X$. The default is None which corresponds to len(X). If size is larger than the length of $X$, $X$ is zero-padded.

modulus: int | None = None¶

The prime modulus $p$ that defines the field $\mathrm{GF}(p)$. The prime modulus must satisfy $p>\text{max}(X)$ and $p=mN+1$ (i.e., the size of the transform $N$ must divide $p-1$). The default is None which corresponds to the smallest $p$ that satisfies the criteria. However, if $x$ is a $\mathrm{GF}(p)$ array, then None corresponds to $p$ from the specified field.

scaled: bool = True¶

Indicates to scale the INTT output by $N$. The default is True. If True, $x=\mathrm{INTT}(\mathrm{NTT}(x))$. If False, $Nx=\mathrm{INTT}(\mathrm{NTT}(x))$.

Returns:¶

The INTT $x$ of the input $X$, with length $N$. The output is a $\mathrm{GF}(p)$ array. It can be viewed as a normal NumPy array with .view(np.ndarray) or converted to a Python list with .tolist().

Notes¶

The Number-Theoretic Transform (NTT) is a specialized Discrete Fourier Transform (DFT) over a finite field $\mathrm{GF}(p)$ instead of over $\mathbb{C}$. The DFT uses the primitive $N$-th root of unity ${\omega }_N=e^{-i2\pi /N}$, but the NTT uses a primitive $N$-th root of unity in $\mathrm{GF}(p)$. These roots are such that ${\omega }_N^N=1$ and ${\omega }_N^k\ne 1$ for $0<k<N$.

In $\mathrm{GF}(p)$, where $p$ is prime, a primitive $N$-th root of unity exists if $N$ divides $p-1$. If that is true, then $p=mN+1$ for some integer $m$. This function finds ${\omega }_N$ by first finding a primitive $p-1$-th root of unity ${\omega }_{p-1}$ in $\mathrm{GF}(p)$ using primitive_root(). From there ${\omega }_N$ is found from ${\omega }_N={\omega }_{p-1}^m$.

The $j$-th value of the scaled $N$-point INTT $x=\mathrm{INTT}(X)$ is

with all arithmetic performed in $\mathrm{GF}(p)$. The scaled INTT has the property that $x=\mathrm{INTT}(\mathrm{NTT}(x))$.

A radix-2 Cooley-Tukey FFT algorithm is implemented, which achieves $O(N\log (N))$.

References¶

• https://cgyurgyik.github.io/posts/2021/04/brief-introduction-to-ntt/

• https://www.nayuki.io/page/number-theoretic-transform-integer-dft

• https://www.geeksforgeeks.org/python-number-theoretic-transformation/

Examples¶

The default modulus is the smallest $p$ such that $p>\text{max}(X)$ and $p=mN+1$. With the input $X=[0,4,3,2]$ and $N=4$, the default modulus is $p=5$.

In [1]: galois.intt([0, 4, 3, 2])
Out[1]: GF([1, 2, 3, 4], order=5)

However, other moduli satisfy $p>\text{max}(X)$ and $p=mN+1$. For instance, $p=13$ and $p=17$. Notice the INTT outputs are different with different moduli. So it is important to perform forward and reverse NTTs with the same modulus.

In [2]: galois.intt([0, 4, 3, 2], modulus=13)
Out[2]: GF([12,  5,  9,  0], order=13)

In [3]: galois.intt([0, 4, 3, 2], modulus=17)
Out[3]: GF([15, 14, 12, 10], order=17)

Instead of explicitly specifying the prime modulus, a $\mathrm{GF}(p)$ array may be explicitly passed in and the modulus is taken as $p$.

In [4]: GF = galois.GF(13)

In [5]: X = GF([10, 8, 11, 1]); X
Out[5]: GF([10,  8, 11,  1], order=13)

In [6]: x = galois.intt(X); x
Out[6]: GF([1, 2, 3, 4], order=13)

In [7]: galois.ntt(x)
Out[7]: GF([10,  8, 11,  1], order=13)

The forward NTT and scaled INTT are the identity transform, i.e. $x=\mathrm{INTT}(\mathrm{NTT}(x))$.

In [8]: GF = galois.GF(13)

In [9]: x = GF([1, 2, 3, 4]); x
Out[9]: GF([1, 2, 3, 4], order=13)

In [10]: galois.intt(galois.ntt(x))
Out[10]: GF([1, 2, 3, 4], order=13)

This is also true in the reverse order, i.e. $x=\mathrm{NTT}(\mathrm{INTT}(x))$.

In [11]: galois.ntt(galois.intt(x))
Out[11]: GF([1, 2, 3, 4], order=13)

The numpy.fft.ifft() function may also be used to compute the inverse NTT over $\mathrm{GF}(p)$.

In [12]: X = np.fft.fft(x); X
Out[12]: GF([10,  8, 11,  1], order=13)

In [13]: np.fft.ifft(X)
Out[13]: GF([1, 2, 3, 4], order=13)