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

bool

References