galois.is_irreducible(poly) seems to return some false negatives in large odd exponent GFs

[geostergiop]

Hi Matt, hope all is well.

Even though it works fine for other groups (e.g. even groups likes GF(2^256) work well), still I 've been getting the following false negative result when using the galois.is_irreducible(poly) over odd groups tο produce irreducible polynomials over GF(2^233).

For example, we know from previous publications and research that x^233+x^74+1 is irreducible over GF(2) for creating the quotient ring of GF(2^233) but the following code returns Null for every polynomial (including the aforementioned one):

def loop_init_trinomial():
    #initial detection loop
    for k in range(1, 233):
        poly = galois.Poly.Degrees([233, k, 0])
        if galois.is_irreducible(poly):
            print("Found one: ", k, poly, poly.string)

Care to share some thoughts?

[mhostetter]

Hey George. Thanks for the report, as always! I do believe this is a bug. I can reproduce.

In [1]: import galois

In [2]: f = galois.Poly.Degrees([233, 74, 0]); f
Out[2]: Poly(x^233 + x^74 + 1, GF(2))

In [3]: galois.is_irreducible(f)
Out[3]: False

In [4]: galois.factors(f)
Out[4]: ([Poly(x^233 + x^74 + 1, GF(2))], [1])

I believe the bug arises in cases when the polynomial degree is prime. I'll report back.

[mhostetter]

@geostergiop it turned out not to be an algorithm issue. Instead, the issue was a np.int64 invaded some integer arithmetic, which coerced all other ints to np.int64. In irreducibility checks, you have to do q**m, and if either is np.int64 not int, the calculation can overflow. The downstream calculations are then incorrect.

See #361 for more details. It will be merged into master in ~20 mins.

[geostergiop]

Ok, thanks Matt. Appreciate it.

So long story short, should I re-run previous experiments that searched for irreducibles in the GF(2^256) or did those algorithms run correctly? I mean, did the np.int64 coersion affect all polynomials regardless of exponents? Are previous uses of galois.is_irreducible(poly) for e.g. [256, x, j, k, 0] affected?

I fear that maybe polynomials with prime numbers in x, j, k below 256 might incorrectly have turned out as false negatives.

[mhostetter]

I can't be certain, to be honest. Did you discover this bug after updating versions? I believe this bug was introduced recently.

[mhostetter]

FWIW, I just ran this script against v0.0.23 (that I believe you said you used before) and the bug was not present.

# test_2.py
import galois

f = galois.Poly.Degrees([233, 74, 0])
print(galois.is_irreducible(f))

#initial detection loop
for k in range(1, 233):
    poly = galois.Poly.Degrees([233, k, 0])
    if galois.is_irreducible(poly):
        print("Found one: ", k, poly)

In [1]: %run test_2.py
True
Found one:  74 Poly(x^233 + x^74 + 1, GF(2))
Found one:  159 Poly(x^233 + x^159 + 1, GF(2))

[geostergiop]

Indeed, I can confirm that v0.0.23 didn't have an issue, just iterated our generated irreducibles outputs from previous runs for prime exponents and they do exist, plenty of them, so I guess we are fine.

[mhostetter]

And to be clear, I was incorrect about prime exponents. That wasn't the issue. The issue was large exponents (that were secretly np.int64). I believe this bug was introduced after the refactor and major speed-ups from v0.0.26.

Again, I appreciate the bug report! 🙏

[geostergiop]

Yep sorry, bad reference!