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

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

Parameters
x: ArrayLike

The input sequence of integers x.

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

The prime modulus p that defines the field GF(p). The prime modulus must satisfy p>max(x) and p=mN+1 (i.e., the size of the transform N must divide p1). The default is None which corresponds to the smallest p that satisfies the criteria. However, if x is a 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 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

intt

Notes

The Number-Theoretic Transform (NTT) is a specialized Discrete Fourier Transform (DFT) over a finite field GF(p) instead of over C. The DFT uses the primitive N-th root of unity ωN=ei2π/N, but the NTT uses a primitive N-th root of unity in GF(p). These roots are such that ωNN=1 and ωNk1 for 0<k<N.

In GF(p), where p is prime, a primitive N-th root of unity exists if N divides p1. If that is true, then p=mN+1 for some integer m. This function finds ωN by first finding a primitive p1-th root of unity ωp1 in GF(p) using primitive_root(). From there ωN is found from ωN=ωp1m.

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

Xk=j=0N1xjωNjk,

with all arithmetic performed in GF(p).

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

References

Examples

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