Quadratic sieving

Kleinjung, Thorsten

doi:10.1090/mcom/3058

Quadratic sieving
HTML articles powered by AMS MathViewer

by Thorsten Kleinjung PDF

Math. Comp. 85 (2016), 1861-1873 Request permission

Abstract:

We propose an efficient variant for the initialisation step of quadratic sieving, the sieving step of the quadratic sieve and its variants, which is also used in sieving-based algorithms for computing class groups of quadratic fields. As an application we computed the class groups of imaginary quadratic fields with 100-, 110-, 120-, and 130-digit discriminants.

References

Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
Karim Belabas, Francisco Diaz y Diaz, and Eduardo Friedman, Small generators of the ideal class group, Math. Comp. 77 (2008), no. 262, 1185–1197. MR 2373197, DOI 10.1090/S0025-5718-07-02003-0
Jean-François Biasse, Improvements in the computation of ideal class groups of imaginary quadratic number fields, Adv. Math. Commun. 4 (2010), no. 2, 141–154. MR 2654130, DOI 10.3934/amc.2010.4.141
E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964, DOI 10.1016/0022-314X(83)90002-1
Michael J. Jacobson Jr., Applying sieving to the computation of quadratic class groups, Math. Comp. 68 (1999), no. 226, 859–867. MR 1604324, DOI 10.1090/S0025-5718-99-01003-0
A. K. Lenstra and H. W. Lenstra, Jr. (eds.), The Development of the Number Field Sieve, Lecture Notes in Math. 1554, Springer, 1993.
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
Kevin S. McCurley, Cryptographic key distribution and computation in class groups, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 459–479. MR 1123090
C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260
Carl Pomerance, J. W. Smith, and Randy Tuler, A pipeline architecture for factoring large integers with the quadratic sieve algorithm, SIAM J. Comput. 17 (1988), no. 2, 387–403. Special issue on cryptography. MR 935347, DOI 10.1137/0217023
Robert D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329–339. MR 866119, DOI 10.1090/S0025-5718-1987-0866119-8