nmod_poly_is_irreducible_rabin
#include <flint/nmod_poly_factor.h>int nmod_poly_is_irreducible_rabin(const nmod_poly_t f)sourceReturns whether f is irreducible, by Rabin's test [Rab1980b]: f of degree n is irreducible if and only if x^{p^n} \equiv x \pmod f and \gcd(x^{p^{n/r}} - x, f) = 1 for every prime r \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 x^{p^e} \bmod f by e successive exponentiations by p, at a cost of about e \log_2 p multiplications modulo f, 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.
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-10-20).
@misc{flint-doc-nmod-poly-factor-nmod-poly-is-irreducible-rabin,
author = {{The FLINT team}},
title = {{nmod\_poly\_is\_irreducible\_rabin (nmod\_poly\_factor.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/nmod_poly_factor/nmod_poly_is_irreducible_rabin.html},
note = {Generated 2026-10-20}
}