Quadratic sieving (Q2796022)

The quadratic sieve [\textit{C. Pomerance}, in: Computational methods in number theory, Part I, Math. Cent. Tracts 154, 89--139 (1982; Zbl 0508.10004)] is one of the workhorse algorithms of number theory, in particular in a variant using multiple polynomials [\textit{R. D. Silverman}, Math. Comput. 48, 329--339 (1987; Zbl 0608.10004)]. While it got somewhat superceded by its descendant, the number field sieve, it still is a fundamental tool, not only for integer factorization but also for the computation of class groups [\textit{M. J. Jacobson jun.}, Math. Comput. 68, No. 226, 859--867 (1999; Zbl 1036.11067)].NEWLINENEWLINEIn this -- by necessity rather technical -- article, the author describes a variant to the self-initialization step of the quadratic sieve, together with heuristic arguments about their improved performance.NEWLINENEWLINEAs an application, the author computes class groups of some imaginary quadratic number fields, assuming -- through bounds of \textit{E. Bach} [Math. Comput. 55, No. 191, 355--380 (1990; Zbl 0701.11075)] -- the generalized Riemann Hypothesis.