FLINT3.7.0-dev
/

nmod_poly_is_irreducible_rabin

Synopsis#include <flint/nmod_poly_factor.h>
int nmod_poly_is_irreducible_rabin(const nmod_poly_t f)source

Returns whether f is irreducible, by Rabin's test [Rab1980b]: ff of degree nn is irreducible if and only if xpn≡x(modf)x^{p^n} \equiv x \pmod f and gcd⁡(xpn/r−x,f)=1\gcd(x^{p^{n/r}} - x, f) = 1 for every prime r∣nr \mid n. Constants are considered irreducible.

Unlike the other irreducibility tests, this function is not a wrapper of the generic implementation: it computes each power xpe mod fx^{p^e} \bmod f by ee successive exponentiations by pp, at a cost of about elog⁡2pe \log_2 p multiplications modulo ff, which makes it much slower than nmod_poly_is_irreducible for large degrees.

References#

  • [Rab1980b] M. O. Rabin. Probabilistic algorithms in finite fields. SIAM Journal on Computing 9 (1980), 273–280.
Cite this page

The FLINT team, “nmod_poly_is_irreducible_rabin (nmod_poly_factor.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_poly_factor/nmod_poly_is_irreducible_rabin.html (generated 2026-11-02).