# galois.is_irreducible¶

galois.is_irreducible(poly)

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

Parameters

poly (galois.Poly) – A polynomial $$f(x)$$ over $$\mathrm{GF}(p^m)$$.

Returns

True if the polynomial is irreducible.

Return type

bool

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]: galois.is_irreducible(f)
Out[3]: True

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

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

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

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