galois.ntt(x: ArrayLike, size: = None, modulus: = None)

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

Parameters:
x: ArrayLike

The input sequence of integers $$x$$.

size: = None

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: = 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.

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

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 $$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)$$.

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 = [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)


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

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

In [9]: x = GF([1, 2, 3, 4, 5, 6])

In [10]: np.fft.fft(x, n=8)
Out[10]: GF([ 4,  8,  4,  1, 14, 11,  2, 15], order=17)