Probabilistic absolute irreducibility test for polynomials (Q1612137)

The paper gives a fast deterministic algorithm to do the following: given a multivariate polynomial over the integers, return ``yes'' if it is proven to be absolutely irreducible. It is shown that most absolutely irreducible polynomials are recognized as such by this algorithm, assuming a certain probability distribution. The algorithm is used by the computer algebra system Maple in order to avoid the more costly decision algorithm for absolute irreducibility in most cases.