gr_poly_is_irreducible, gr_poly_is_irreducible_ben_or, gr_poly_is_irreducible_ddf, gr_poly_is_irreducible_rabin

The ben_or version uses Ben-Or's test [BenOr1981], computing \gcd(f, x^{q^i} - x) for i \le n/2 with the Frobenius iterates obtained by modular composition or exponentiation. The ddf version runs the coarse phase of the baby-step giant-step distinct-degree factorisation (gr_poly_factor_distinct_deg) and stops at the first factor found, which is fast on inputs with small factors. The rabin version uses Rabin's test [Rab1980b]: f of degree n is irreducible if and only if x^{q^n} \equiv x \bmod f and \gcd(x^{q^{n/r}} - x, f) = 1 for every prime r \mid n; the Frobenius powers are computed by modular composition from the ladder x^{q^{2^i}}, so that the test costs O((1 + \omega(n)) \log n) compositions after the initial x^q, against about 2 \sqrt{n} for the distinct-degree test, but it does not stop early on inputs with small factors.

The default version first looks for roots by evaluation when the field is a small prime field; for degree below 600 it then calls the ddf version, and from 600 on it checks squarefreeness, removes inputs with factors of degree at most 4 with a few gcds, and calls the rabin version.

@misc{flint-doc-gr-poly-gr-poly-is-irreducible,
  author       = {{The FLINT team}},
  title        = {{gr\_poly\_is\_irreducible, gr\_poly\_is\_irreducible\_ben\_or, gr\_poly\_is\_irreducible\_ddf, gr\_poly\_is\_irreducible\_rabin (gr\_poly.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/gr_poly/gr_poly_is_irreducible.html},
  note         = {Generated 2026-10-20}
}