The determination of the irreducibility of a polynomial with coefficients in a given domain is an important natural problem. This paper presents what seems to be the first polynomial algorithm for testing the absolute irreducibility of polynomials in Z[X₁, . . . , X_n] (i.e., irreducibility over the complex numbers). In fact, the algorithm is a parallel one that runs in time polynomial in the logarithm of the degree of the input polynomial and the logarithm of the coefficient length. It requires polynomially many processors, thus showing that absolute irreducibility is in NC.

Another of the paper’s results concerns a theorem of Ostrowski (1919), which states that an absolutely irreducible integral polynomial remains absolutely irreducible modulo all but finitely many prime numbers. An upper bound for the least prime number implied in this theorem is derived, which considerably improves previous bounds. Both contributions are important, but a reader not familiar with the subject would find the paper difficult to read as many technical details are presented parsimoniously. The author states that research is in progress to overcome some difficulties that occurred during computer implementation of the algorithm.