-
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 tolen(x)
. Ifsize
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, thenNone
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()
.
See also
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¶
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)
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)