How long does it take to compute a class number? I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the discriminant, I guess.)
This would also be of interest in special cases like fields with a given degree or signature. The simplest one would be the family of imaginary quadratic fields: in this setting there is Swan's algorithm (which actually computes reduced bases for all ideals of least norms in their class), which takes (I think) at most $m^3$ steps to do $\mathbb{Q}(\sqrt{-m})$ when implemented without more thought. Is there a better algorithm known, or is there a speedy implementation of Swan's algorithm? 
 A: In the case of quadratic fields there is a very nice paper of Andy Booker (see http://www.ams.org/journals/mcom/2006-75-255/S0025-5718-06-01850-3/home.html ) which uses the Burgess bounds on character sums (among other ideas) to compute the class number.  The running time is always $O(D^{1/2+\epsilon})$ and if the GRH is true then the algorithm executes in time $O(D^{1/4+\epsilon})$.   I think this is the best that is known.  If one wants all class numbers up to a point then there are other clever algorithms based on the trace formula for doing this (see work of Jacobson, Ramachandran and Williams; Springer Lecture notes in CS vol 4076).  
Note: As Edgardo observes there are faster randomized algorithms, and also earlier algorithms that rely on GRH (either running in heuristically subexponential time, or in time $D^{1/4+\epsilon}$).  But these use GRH in an essential way in that the algorithm halts only if GRH is true.  A subtle difference in Booker's algorithm is that it is guaranteed to halt; only the analysis of how long it takes to halt depends on GRH.  
A: J. Buchmann and M. Pohst in a 1989 paper show that the class group can be computed in time of order $D^{1+\epsilon},$ where $D$ is the discriminant.
A: In the special case of an imaginary quadratic field of discriminant $-D$, one can use reduction theory to compute the class number in around $D^{1/2}$ steps.  Computing the class number boils down to counting binary quadratic forms $ax^2 + bxy + cy^2$ with $a \geq 1$, $b^2 - 4ac = -D$, and $|b| \leq a \leq c$.  In particular, this means $4ac = b^2 + D \leq ac + D$, so $ac \leq D/3$, and so $a \leq \sqrt{D/3}$.  For each $a$, given its prime factorization, it is easy to  quickly check if $b^2 \equiv D \pmod{4a}$ is solvable, and find all $b$'s that solve this quadratic congruence.  Then given $b$ and $a$, we find $c$ by $c = (b^2+D)/(4a)$.  The problem of getting the prime factorization of $a$ is not a problem since we want to do this for each $a \leq \sqrt{D/3}$. It is easy to get the prime factorizations of all $a$'s at once by the sieve of Eratosthenes.  I believe this method takes at most $D^{1/2} \log^C D$ steps for some small $C$.
A: Index calculus works, and much faster (although it is randomized); search for "subexponential class group".
