Fast parallel absolute irreducibility testing.pdf

Fast Parallel Absolute Irreducibility Testing * U Erich Kaltofen niversity of Toronto e T Department of Computer Scienc oronto, Ontario M5S1A4, Canada W Abstract e present a fast parallel deterministic algorithm for testing multivariate integral polyno- - c mials for absolute irreducibility, that is irreducibility over the complex numbers. More pre isely, we establish that the set of absolutely irreducible integral polynomials belongs to the e i complexity class NC of Boolean circuits of polynomial size and logarithmic depth. Therefor t also belongs to the class of sequentially polynomial-time problems. Our algorithm can be - n extended to compute in parallel one irreducible complex factor of a multivariate integral poly omial. However, the coefficients of the computed factor are only represented modulo a not r necessarily irreducible polynomial specifying a splitting field. A consequence of our algo- ithm is that multivariate polynomials over finite fields can be tested for absolute irreducibility p b in deterministic sequential polynomial time in the size of the input. We also obtain a shar ound for the last prime p for which, when taking an absolutely irreducible integral polyno- f o mial modulo p , the polynomial’s irreducibility in the algebraic closure of the finite field o rder p is not preserved. Keywords: Absolute Irreducibility, Polynomial-Time Complexity, Parallel Algorithm. * hhhhhhhhhhhhhhh This research was partially supported by the National Science and Engineering Council of Canada under grant A 3-643-126-90. uthor’s current address: Rensselaer Polytechnic Institute, Department of Computer Science, Troy, New York, T 12181. his paper appears in the Journal of Symbolic Computation, vol. 1, nr. 1, pp. 57-67 (1985). 1- 2 - . Introduction - t The determination of the irreducibility of a polynomial with coefficients in a unique fac orization domain is an old problem. Recently, several new algorithms for univariate and e f multivariate factorization over va