Parallel Construction of Irreducible Polynomials

Abstract

Let arithmetic pseudo-NC^k denote the problems that can be solved by log space uniform arithmetic circuits over the finite prime field GF(p) of depth O(log^k (n + p)) and size polynomial in (n + p). We show that the problem of constructing an irreducible polynomial of specified degree over GF(p) belongs to pseudo-NC^2.5. We prove that the problem of constructing an irreducible polynomial of specified degree over GF(p) whose roots are guaranteed to form a normal basis for the corresponding field extension pseudo-NC^2 -reduces to the problem of factor refinement. We show that factor refinement of polynomials is in arithmetic NC^3. Our algorithm works over any field and compared to other known algorithms it does not assume the ability to take p'th roots when the field has characteristic p