galois.is_irreducible¶
-
galois.
is_irreducible
(poly)[source]¶ Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible.
This function implementats 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