# 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?

• Here is an open question I have wondered about: What is an upper complexity bound for the calculation of the class number of a cyclotomic field of conductor $m$? Since the degrees of these fields differ, currently known results are not yet able to address this problem. – graduate student Nov 3 '13 at 2:55
• This sounds nice; you should probably ask it as a separate question since the focus here (for me at least, and it seems for the papers linked in the answers also) was on fields with bounded degree (also, a new question has probably a better chance to be aswered, and will be more useful when answered, than a comment on an old question). – Jean Raimbault Nov 4 '13 at 10:39

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.

• Great answer for this special case, thanks! It should be noted that the algorithm computes the class-number alone (using analytic number theory) without using a basis or an enumeration for the class-group (contrary to those in Igor Rivin and Matt Young's answers). – Jean Raimbault Oct 30 '13 at 9:42
• Also, the liked paper by Booker contains reference to the (conditional) sub-exponential algorithm mentioned in the (somewhat cryptic) answer by Edgardo below. – Jean Raimbault Oct 31 '13 at 8:50

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.

• Thanks! I guess this answer the question pretty well; I'll wait to see if anybody has anything else to contribute before accepting it since the formulation of my question was pretty open. A few remarks on the algorithm for those who don't want to have to go to the likned paper: it computes a basis for the class-group, and then computes the order of each of its elements. It uses the order generated by the powers of a root (if this is the whole integer ring then it is OK, otherwise they rely on some other work by Pohst and H. Zassenhaus). – Jean Raimbault Oct 29 '13 at 17:20

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$.

• Thanks! I believe this is the algorithm given in H. Cohen's book (where I should have looked before asking...). It feels like it should be optimal if you want to get reduced bases for the (minimal norm) ideal classes in addition. – Jean Raimbault Oct 30 '13 at 9:45

Index calculus works, and much faster (although it is randomized); search for "subexponential class group".

• Any chance that this answer can be made more informative or explanatory? – Todd Trimble Oct 29 '13 at 20:52