galois.intt(X: ArrayLike, size: = None, modulus: = None, scaled: bool = True)

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

Parameters:
X: ArrayLike

The input sequence of integers $$X$$.

size: = 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: = None

The prime modulus $$p$$ that defines the field $$\mathrm{GF}(p)$$. The prime modulus must satisfy $$p > \textrm{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^{-i 2 \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 \neq 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

$x_j = \frac{1}{N} \sum_{k=0}^{N-1} X_k \omega_N^{-kj} ,$

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 \mathrm{log}(N))$$.

References

Examples

The default modulus is the smallest $$p$$ such that $$p > \textrm{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 > \textrm{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)