Aarhus University Seal / Aarhus Universitets segl

Parallel Construction of Irreducible Polynomials

Research output: Working paper/Preprint Working paperResearch

  • Department of Computer Science
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.
Original languageEnglish
PublisherDepartment of Computer Science, Aarhus University
Number of pages25
Publication statusPublished - 1991

See relations at Aarhus University Citationformats

ID: 36650776