Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Quadratic sieving


Author: Thorsten Kleinjung
Journal: Math. Comp. 85 (2016), 1861-1873
MSC (2010): Primary 11Y05, 11Y16
DOI: https://doi.org/10.1090/mcom/3058
Published electronically: December 7, 2015
MathSciNet review: 3471111
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355-380. MR 1023756 (91m:11096), https://doi.org/10.2307/2008811
  • [2] 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 (2009c:11179), https://doi.org/10.1090/S0025-5718-07-02003-0
  • [3] 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 (2011e:11192), https://doi.org/10.3934/amc.2010.4.141
  • [4] 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 (85j:11012), https://doi.org/10.1016/0022-314X(83)90002-1
  • [5] Michael J. Jacobson Jr., Applying sieving to the computation of quadratic class groups, Math. Comp. 68 (1999), no. 226, 859-867. MR 1604324 (99i:11120), https://doi.org/10.1090/S0025-5718-99-01003-0
  • [6] A. K. Lenstra and H. W. Lenstra, Jr. (eds.), The Development of the Number Field Sieve, Lecture Notes in Math. 1554, Springer, 1993.
  • [7] H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649-673. MR 916721 (89g:11125), https://doi.org/10.2307/1971363
  • [8] 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 (92e:11149)
  • [9] 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 (84i:10005)
  • [10] 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 (89f:11168), https://doi.org/10.1137/0217023
  • [11] Robert D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329-339. MR 866119 (88c:11079), https://doi.org/10.2307/2007894

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y05, 11Y16

Retrieve articles in all journals with MSC (2010): 11Y05, 11Y16


Additional Information

Thorsten Kleinjung
Affiliation: Laboratory for Cryptologic Algorithms, Station 14, EPFL, CH-1015 Lausanne, Swit- zerland

DOI: https://doi.org/10.1090/mcom/3058
Received by editor(s): November 21, 2013
Received by editor(s) in revised form: January 6, 2015
Published electronically: December 7, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society