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.

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$$.

Examples

# Conway polynomials are always irreducible (and primitive)
In : f = galois.conway_poly(2, 5); f
Out: 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 : f.roots()
Out: GF([], order=2)

In : f.is_irreducible()
Out: True

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

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

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

In : f.is_irreducible()
Out: False