fq_poly_is_irreducible, fq_poly_is_irreducible_ddf, fq_poly_is_irreducible_ben_or
#include <flint/fq_poly_factor.h>Return whether f is irreducible. Unlike gr_poly_is_irreducible, these functions return 1 for all polynomials of length at most 2, including constants and zero.
fq_poly_is_irreducible calls gr_poly_is_irreducible, which uses the distinct-degree test below degree 600 and Rabin's test above it. fq_poly_is_irreducible_ddf uses the coarse phase of the baby-step giant-step distinct-degree factorisation, which stops at the first factor found, and fq_poly_is_irreducible_ben_or Ben-Or's test, computing \gcd(f, x^{q^i} - x) for i \le \deg f / 2 [BenOr1981]. See Factoring polynomials over finite fields.
References#
- [BenOr1981] M. Ben-Or. Probabilistic algorithms in finite fields. 22nd Annual Symposium on Foundations of Computer Science (FOCS 1981), IEEE, 394–398.
The FLINT team, “fq_poly_is_irreducible, fq_poly_is_irreducible_ddf, fq_poly_is_irreducible_ben_or (fq_poly_factor.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fq_poly_factor/fq_poly_is_irreducible.html (generated 2026-10-20).
@misc{flint-doc-fq-poly-factor-fq-poly-is-irreducible,
author = {{The FLINT team}},
title = {{fq\_poly\_is\_irreducible, fq\_poly\_is\_irreducible\_ddf, fq\_poly\_is\_irreducible\_ben\_or (fq\_poly\_factor.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fq_poly_factor/fq_poly_is_irreducible.html},
note = {Generated 2026-10-20}
}