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


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


True if the polynomial is irreducible.

Return type



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\).



# 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