ECCC-Report TR03-064https://eccc.weizmann.ac.il/report/2003/064Comments and Revisions published for TR03-064en-usMon, 08 Sep 2003 19:57:30 +0300
Paper TR03-064
| Upper Bounds on the Complexity of some Galois Theory Problems |
Vikraman Arvind,
Piyush Kurur
https://eccc.weizmann.ac.il/report/2003/064Given 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.
Mon, 08 Sep 2003 19:57:30 +0300https://eccc.weizmann.ac.il/report/2003/064