Fast Parallel Absolute Irreducibility Testing
Eric hK altofen · 1985
We p resent a fast parallel deterministic algorithm for testing multivariate integral polynomials for absolute irreducibility ,t hat is irreducibility ove rt he comple xn umbers. More precisely, we establish that the set of absolutely irreducible integral polynomials belongs to the complexity class NC of Boolean circuits of polynomial size and logarithmic depth. Therefore it also belongs to the class of sequentially polynomial-time problems. Our algorithm can be extended to compute in parallel one irreducible comple xf actor of a multivariate integral polynomial. However, the coefficients of the computed factor are only represented modulo a not necessarily irreducible polynomial specifying a splitting field. Ac onsequence of our algorithm is that multivariate polynomials ove rfi nite fields can be tested for absolute irreducibility in deterministic sequential polynomial time in the size of the input. We also obtain a sharp bound for the last prime p for which, when taking an absolutely irreducible integral polynomial modulo p ,t he polynomial’ si rreducibility in the algebraic closure of the finite field of order p is not preserved. Ke ywords :A bsolute Irreducibility ,P olynomial-Time Complexity ,P arallel Algorithm.