In this paper, we present novel algorithms for finding small relations and ideal factorizations in the ideal class group of an order in an imaginary quadratic field, where both the norms of the prime ideals and the size of the coefficients involved are bounded. We show how our methods can be used to improve the computation of large-degree isogenies and endomorphism rings of elliptic curves defined over finite fields. For these problems, we obtain improved heuristic complexity results in almost all cases and significantly improved performance in practice. The speed-up is especially high in situations where the ideal class group can be computed in advance.

Until recently, the ‘plus part’ of the class numbers of cyclotomic fields had only been determined for fields of root discriminant small enough to be treated by Odlyzko’s discriminant bounds.

However, by finding lower bounds for sums over prime ideals of the Hilbert class field, we can now establish upper bounds for class numbers of fields of larger discriminant. This new analytic upper bound, together with algebraic arguments concerning the divisibility properties of class numbers, allows us to unconditionally determine the class numbers of many cyclotomic fields that had previously been untreatable by any known method.

In this paper, we study in particular the cyclotomic fields of composite conductor.

It is proved that the 3-part of the class number of a quadratic field $\mathbb{Q}(\sqrt{D})$ is $O(|D|^{55/112 + \ep})$ in general and $O(|D|^{5/12+\ep})$ if $|D|$ has a divisor of size $|D|^{5/6}$. These bounds follow as results of nontrivial estimates for the number of solutions to the congruence $x^a \,{\con}\, y^b$ modulo $q$ in the ranges $x \,{\leqslant}\,X$ and $y\,{\leqslant}\, Y$, where $a,b$ are nonzero integers and $q$ is a square-free positive integer. Furthermore, it is shown that the number of elliptic curves over $\Q$ with conductor $N$ is $O(N^{55/112 + \ep})$ in general and $O(N^{5/12 + \ep})$ if $N$ has a divisor of size $N^{5/6}$. These results are the first improvements to the trivial bound $O(|D|^{1/2 + \ep})$ and the resulting bound $O(N^{1/2 + \ep})$ for the 3-part and the number of elliptic curves, respectively.

This corrigendum corrects a mistake in K. Belabas, On the mean 3-rank of quadratic fields, Compositio Math. 118 (1999), 1–9.