Given an algebraic number field K, such that [K : Q] is constant, we show that the problem of computing the units group O_K~* is in the complexity class SPP. As a consequence, we show that principal ideal testing for an ideal in O_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 to have a quantum polynomial-time algorithm, is also in SPP.
展开▼
