Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
iyanmv opened this issue Apr 2, 2024 · 5 comments
Open

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

iyanmv opened this issue Apr 2, 2024 · 5 comments

Comments

@iyanmv
Copy link
Contributor

iyanmv commented Apr 2, 2024

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

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
Copy link
Owner

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
Copy link
Contributor Author

iyanmv commented Apr 5, 2024

@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
Copy link
Owner

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
Copy link
Owner

@iyanmv had any more thoughts about this?

@iyanmv
Copy link
Contributor Author

iyanmv commented Jul 1, 2024

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants