Issue with NTT and GF(2) (and other FieldArray)

[iyanmv]

Hi,

If the array passed to ntt is a GF(2) array, then the default modulus will never satisfy the required criteria (unless the array has size 1). This is because the characteristic of the field is used, i.e., p=2, as modulus in

galois/src/galois/_ntt.py

Line 115 in 25baec4

modulus = type(x).characteristic

which causes _ntt to never enter this loop to compute a valid modulus

galois/src/galois/_ntt.py

Lines 249 to 254 in 25baec4

	if modulus is None:
	m = int(np.ceil(np.max(x) / size)) # The smallest m such that modulus > max(x)
	while not is_prime(m * size + 1):
	m += 1
	modulus = m * size + 1
	m = (modulus - 1) // size

This is documented in the docstring, though, so perhaps I'm not understanding something here:

(...) However, if $x$ is a $\mathrm{GF}(p)$ array, then None corresponds to $p$ from the specified field.

I would expect that calling ntt should work correctly, by default, on any FieldArray. For example, I think this code should work:

from galois import GF2, ntt

ntt(GF2.Random(10))

But at the moment it raises a ValueError that the user did not passed.

ValueError: Argument 'modulus' must equal m * size + 1, where 'size' is the size of the NTT transform.

A workaround, is to manually choose a valid modulus, e.g.

import numpy as np
from galois import GF2, ntt, intt

arr = GF2.Random(10)
assert np.array_equal(arr, intt(ntt(arr, modulus=11)))

This also happens with other fields. For example,

from galois import GF

gf = GF(3)

arr = gf.Random(10)
ntt(gf)

Commenting the two lines from ntt solves the issue for me:

galois/src/galois/_ntt.py

Lines 114 to 115 in 25baec4

	if modulus is None and isinstance(x, FieldArray):
	modulus = type(x).characteristic

[mhostetter]

Caveat: I don't have any practical experience with the NTT. So my knowledge may be limited.

If the array passed to ntt is a GF(2) array, then the default modulus will never satisfy the required criteria (unless the array has size 1).

It is my understanding that there is no NTT transform of a length-10 array over GF(2), since there isn't a primitive 10-th root in GF(2).

I believe you have to "cast" (the mathematical term is not coming to mind) the GF(2) array into a larger field to compute the NTT. In your example, you need to "cast" to GF(11), or a larger field. I fear performing this promotion silently could be misleading / have unintended effects.

For example, if the user provided an array over GF(p1), but the values were small and the array was short, can a smaller modulus p2 < p1 exist that would satisfy the criteria? If so, the function would choose p2 (which is different than the input of p1) and the NTT output would be different than if computed using p1. That seems like an unexpected result.

A workaround, is to manually choose a valid modulus

Another workaround is to pass a NumPy array or list, not FieldArray. So ntt(arr.view(np.ndarray)) or ntt(arr.tolist()).

What are your thoughts?

[iyanmv]

@mhostetter Let me think about it for a while, I'm also not that familiar with the NTT. As usual, you bring nice points, and I was just thinking about some specific use cases.

[mhostetter]

Here's an example of how different (valid) moduli can affect the NTT output.

import galois

x = galois.GF(2).Random(10)
print(x)

print(galois.ntt(x, modulus=11))
print(galois.ntt(x, modulus=31))
print(galois.ntt(x, modulus=71))

[0 1 0 1 1 1 1 0 0 0]
[ 5  1 10  9  2 10  5  4  5  4]
[ 5  5  8  7  6 30 19 28 29 18]
[ 5 50 49 48 51 70  3 38 39  2]

So if the initial array x was over GF(71) and passed to ntt(), the auto-selected modulus would be 11, leading to a different output than what would have been produced if 71 was kept.

[mhostetter]

@iyanmv had any more thoughts about this?

[iyanmv]

Sorry, I still didn't have time to check the theory in detail and see if it would make sense. But it is in my TODO list, hopefully soon