galois.ntt¶

galois.ntt(x, size=None, modulus=None)¶

Computes the Number-Theoretic Transform (NTT) of \(x\).

Parameters

x : Union[Sequence[int], numpy.ndarray, galois.FieldArray]

The input sequence of integers \(x\).

size : Optional[int]

The size \(N\) of the NTT 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 : Optional[int]

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.

Returns

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

Return type

galois.FieldArray

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 galois.primitive_root(). From there \(\omega_N\) is found from \(\omega_N = \omega_{p - 1}^m\).

The \(k\)-th value of the \(N\)-point NTT \(X = \mathrm{NTT}(x)\) is

\[X_k = \sum_{j=0}^{N-1} x_j \omega_N^{jk} ,\]

with all arithmetic performed in \(\mathrm{GF}(p)\).

Currently, the algorithm implemented is \(O(N^2)\). A future improvement will be to add a radix-2 Cooley-Tukey implementation, which will have \(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 = [1, 2, 3, 4]\) and \(N = 4\), the default modulus is \(p = 5\).

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

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

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

In [3]: galois.ntt([1, 2, 3, 4], modulus=17)
Out[3]: GF([10,  6, 15,  7], 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]: galois.ntt(GF([1, 2, 3, 4]))
Out[5]: GF([10,  8, 11,  1], order=13)

The size keyword argument allows convenient zero-padding of the input (to a power of two, for example).

In [6]: galois.ntt([1, 2, 3, 4, 5, 6], size=8)
Out[6]: GF([ 4,  8,  4,  1, 14, 11,  2, 15], order=17)

In [7]: galois.ntt([1, 2, 3, 4, 5, 6, 0, 0])
Out[7]: GF([ 4,  8,  4,  1, 14, 11,  2, 15], order=17)