A heuristic irreducibility test for univariate polynomials (Q1186702)

Let \(f(x)\) be a polynomial: if \(f(a)\), for an \(a\) sufficiently far from the zeros of \(f\), is prime then \(f\) is irreducible. It is shown how to choose \(a\), and how large values of \(f(a)\) may be avoided by a change of variable. Timings are given for comparison with the Berlekamp-Hensel procedure as implemented in MACSYMA, MAPLE, and REDUCE. The possibility of factorizing \(f\) by factorizing \(f(a)\) is discussed. If \(f\) has many factors then choosing the right combination of factors of \(f(a)\) can be difficult.