Sieving methods for class group computation
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].
- scientific article; zbMATH DE number 2086881
- On the Computation of the Class Number of an Algebraic Number Field
- Computation of Real Quadratic Fields with Class Number One
- scientific article; zbMATH DE number 475432
- Square Root Algorithms for the Number Field Sieve
- Quadratic sieving
- scientific article; zbMATH DE number 475435
- On a strategy in the sieving procedure for the factorization of large natural numbers
- scientific article; zbMATH DE number 733561
- A one line factoring algorithm
- Quadratic sieving
- Improved techniques for computing the ideal class group and a system of fundamental units in number fields
- Reducing number field defining polynomials: an application to class group computations
- scientific article; zbMATH DE number 3843861 (Why is no real title available?)
- Generalised Sifting in Black-Box Groups
- The Elkies curve has rank 28 subject only to GRH
- Sieving in Function Fields
- Small generators of the ideal class group
- Quadratic class numbers and character sums
- Sieving Procedures on a Digital Computer
This page was built for publication: Sieving methods for class group computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247780)
