Given an algebraic number field K, such that [K : ℚ] is constant, we show that the problem of computing the units group φ*K is in the complexity class SPP. As a consequence, we show that principal ideal testing for an ideal in φK is in SPP. Furthermore, assuming the GRH, the class number of K, and a presentation for the class group of K can also be computed in SPP. A corollary of our result is that solving PELL'S EQUATION, recently shown by Hallgren [12] to have a quantum polynomial-time algorithm, is also in SPP. © Springer-Verlag Berlin Heidelberg 2004.