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

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

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

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

In : galois.is_irreducible(f)
Out: False