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
Additional Information
- Thorsten Kleinjung
- Affiliation: Laboratory for Cryptologic Algorithms, Station 14, EPFL, CH-1015 Lausanne, Swit- zerland
- MR Author ID: 704259
- Received by editor(s): November 21, 2013
- Received by editor(s) in revised form: January 6, 2015
- Published electronically: December 7, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 1861-1873
- MSC (2010): Primary 11Y05, 11Y16
- DOI: https://doi.org/10.1090/mcom/3058
- MathSciNet review: 3471111