Sieving methods for class group computation (Q4247780)

This multi-authored paper contains an improved version of an algorithm to find the regulator \(R\) and the class number \(h\) of a number field \(K\) by a method reminiscent of the quadratic sieve, largely due to \textit{J. Buchmann} [A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Sémin. Théor. Nombres Prog. Math. 91, 27-41 (1990; Zbl 0727.11059)]. A sufficient set of prime ideals forms a factor base \(FB\) of rank \(k\) and the unit rank of \(K\) is \(r\). Then to any \(\alpha\) factorable in the factor base, we make correspond the vector of rank \(k+d\) formed by the exponents of the \(k\) factors of \(\alpha\) and the \(d\) values of \(\log|\alpha^{(j)}|\) over conjugates. Then a Hermite reduction on the exponents produces \(h\) (actually the class group) and \(R\). The trick is to generate the set \(\{\alpha\}\). In the quadratic case, the ideals generated by simple combinations of the \(FB\)-primes lead to quadratic forms (say) \(f(X,Y)\) and then we demand \(f(X,1)\) be factorable in \(FB\) (and conjugates). Actually, the use of norm forms is also effective for higher degree fields. The Dirichlet \(L\)-series formula for \(hR\) serves as a guide to accuracy. Techniques for generating \(FB\)-smooth values \(\alpha\) are not described in detail, but they are apparently very effective in quadratic fields and ``easy'' cubic fields \(\mathbb{Q} (m^{1/3})\) for \(m\) close to a perfect cube. For the entire collection see [Zbl 0903.00035].