Assuming the generalized Riemann hypothesis, we prove the following complexity bounds: The order of the Galois group of an arbitrary polynomial f(x) ∈ ℤ[x] can be computed in P#P. Furthermore, the order can be approximated by a randomized polynomial-time algorithm with access to an NP oracle. 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. For all polynomiab f with abelian Galois group we show that a generator set for the Galois group can be computed in randomized polynomial time. © Springer-Verlag Berlin Heidelberg 2003.