galois.is_irreducible¶
- class galois.is_irreducible(poly)¶
Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible.
A polynomial \(f(x) \in \mathrm{GF}(p)[x]\) is reducible over \(\mathrm{GF}(p)\) if it can be represented as \(f(x) = g(x) h(x)\) for some \(g(x), h(x) \in \mathrm{GF}(p)[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-\(n\) polynomial \(f(x)\) over \(\mathrm{GF}(p)\) for prime \(p\) is irreducible if and only if \(f(x)\ |\ (x^{p^n} - x)\) and \(\textrm{gcd}(f(x),\ x^{p^{m_i}} - x) = 1\) for \(1 \le i \le k\), where \(m_i = n/p_i\) for the \(k\) prime divisors \(p_i\) of \(n\).
- Parameters
poly (galois.Poly) – A polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
- Returns
True
if the polynomial is irreducible.- Return type
References
Rabin. Probabilistic algorithms in finite fields. SIAM Journal on Computing (1980), 273–280. https://apps.dtic.mil/sti/pdfs/ADA078416.pdf
Gao and D. Panarino. Tests and constructions of irreducible polynomials over finite fields. https://www.math.clemson.edu/~sgao/papers/GP97a.pdf
https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields
Examples
# Conway polynomials are always irreducible (and primitive) In [502]: f = galois.conway_poly(2, 5); f Out[502]: Poly(x^5 + x^2 + 1, GF(2)) # f(x) has no roots in GF(2), a requirement of being irreducible In [503]: f.roots() Out[503]: GF([], order=2) In [504]: galois.is_irreducible(f) Out[504]: True
In [505]: g = galois.conway_poly(2, 4); g Out[505]: Poly(x^4 + x + 1, GF(2)) In [506]: h = galois.conway_poly(2, 5); h Out[506]: Poly(x^5 + x^2 + 1, GF(2)) In [507]: f = g * h; f Out[507]: Poly(x^9 + x^5 + x^4 + x^3 + x^2 + x + 1, GF(2)) # Even though f(x) has no roots in GF(2), it is still reducible In [508]: f.roots() Out[508]: GF([], order=2) In [509]: galois.is_irreducible(f) Out[509]: False