galois.is_irreducible¶

galois.is_irreducible(poly: Poly) → bool¶

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

Parameters¶

poly: Poly¶

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

Returns¶

True if the polynomial is irreducible.

See also

is_primitive, irreducible_poly, irreducible_polys

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 $\text{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

• Rabin, M. Probabilistic algorithms in finite fields. SIAM Journal on Computing (1980), 273–280. https://apps.dtic.mil/sti/pdfs/ADA078416.pdf

• Gao, S. and Panarino, D. Tests and constructions of irreducible polynomials over finite fields. https://www.math.clemson.edu/~sgao/papers/GP97a.pdf

• Section 4.5.1 from https://cacr.uwaterloo.ca/hac/about/chap4.pdf

• https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields

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 + 8x + 6, GF(2^4))

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

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

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