galois.Poly.is_irreducible() bool

Determines whether the polynomial $$f(x)$$ over $$\mathrm{GF}(p^m)$$ is irreducible.

Why is this a method and not a property?

This is a method to indicate it is a computationally-expensive task.

Returns:

True if the polynomial is irreducible.

Notes

A polynomial $$f(x) \in \mathrm{GF}(p^m)[x]$$ is reducible over $$\mathrm{GF}(p^m)$$ if it can be represented as $$f(x) = g(x) h(x)$$ for some $$g(x), h(x) \in \mathrm{GF}(p^m)[x]$$ of strictly lower degree. If $$f(x)$$ is not reducible, it is said to be irreducible. Since Galois fields are not algebraically closed, such irreducible polynomials exist.

This function implements Rabin’s irreducibility test. It says a degree-$$m$$ polynomial $$f(x)$$ over $$\mathrm{GF}(q)$$ for prime power $$q$$ is irreducible if and only if $f(x)\ |\ (x^{q^m} - x)$ and $$\textrm{gcd}(f(x),\ x^{q^{m_i}} - x) = 1$$ for $$1 \le i \le k$$, where $$m_i = m/p_i$$ for the $$k$$ prime divisors $$p_i$$ of $$m$$.

References

Examples

# Conway polynomials are always irreducible (and primitive)
In [1]: f = galois.conway_poly(2, 5); f
Out[1]: Poly(x^5 + x^2 + 1, GF(2))

# f(x) has no roots in GF(2), a necessary but not sufficient condition of being irreducible
In [2]: f.roots()
Out[2]: GF([], order=2)

In [3]: f.is_irreducible()
Out[3]: True

In [4]: g = galois.irreducible_poly(2**4, 2, method="random"); g
Out[4]: Poly(x^2 + x + 12, GF(2^4))

In [5]: h = galois.irreducible_poly(2**4, 3, method="random"); h
Out[5]: Poly(x^3 + 2x^2 + 10x + 1, GF(2^4))

In [6]: f = g * h; f
Out[6]: Poly(x^5 + 3x^4 + 4x^3 + 12, GF(2^4))

In [7]: f.is_irreducible()
Out[7]: False