Open iyanmv opened 3 months ago
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?
@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.
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.
@iyanmv had any more thoughts about this?
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
Hi,
If the array passed to
ntt
is aGF(2)
array, then the defaultmodulus
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 inhttps://github.com/mhostetter/galois/blob/25baec4b46d5238df78e6a2b92717cb051caf799/src/galois/_ntt.py#L115
which causes
_ntt
to never enter this loop to compute a validmodulus
https://github.com/mhostetter/galois/blob/25baec4b46d5238df78e6a2b92717cb051caf799/src/galois/_ntt.py#L249-L254
This is documented in the docstring, though, so perhaps I'm not understanding something here:
I would expect that calling
ntt
should work correctly, by default, on any FieldArray. For example, I think this code should work:But at the moment it raises a
ValueError
that the user did not passed.A workaround, is to manually choose a valid modulus, e.g.
This also happens with other fields. For example,
Commenting the two lines from
ntt
solves the issue for me:https://github.com/mhostetter/galois/blob/25baec4b46d5238df78e6a2b92717cb051caf799/src/galois/_ntt.py#L114-L115