期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Given a polynomial f(X) with rational coefficients as input we study the problem of (a) finding the order of the Galois group of f(X), and (b) determining the Galois group of f(X) by finding a small generator set. Assuming the generalized Riemann hypothesis, we prove the following complexity bounds: 1. The order of the Galois group of an arbitrary polynomial f(X) in Z[X] can be computed by a polynomial-time oracle machine with a #P oracle. Hence, the order can be approximated by a randomized polynomial-time algorithm with access to an NP oracle. 2. For polynomials f with solvable Galois group we show that the order can be computed exactly by a randomized polynomial-time algorithm with access to an NP oracle. 3. For all polynomials f with abelian Galois group we show that a generator set for the Galois group (as a permutation group acting on the roots of f) can be computed in randomized polynomial time. These results also hold for polynomials f\in K[X], where the field K is specified by giving the minimal polynomial of a primitive element of K.
关键词：abelian groups. , exact and approximate counting , Galois groups , randomizedalgorithm , solvable groups
