Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR03-064 | 23rd June 2003 00:00

#### Upper Bounds on the Complexity of some Galois Theory Problems

TR03-064
Authors: Vikraman Arvind, Piyush Kurur
Publication: 8th September 2003 19:57
Keywords:

Abstract:

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

2. For polynomials f with solvable Galois group we show that the order
can be computed exactly by a randomized polynomial-time algorithm with