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-11-02}
}