galois.intt¶

galois.intt(X: ArrayLike, size: int | None = None, modulus: int | None = None, scaled: bool = True) → FieldArray¶

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 > \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().

See also

ntt

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

• 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 > \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)