Skip to main content
SpringerLink
Log in

The number field sieve

  • Conference paper
  • First Online:
The development of the number field sieve

Part of the book series: Lecture Notes in Mathematics ((LNM,volume 1554))

Abstract

The number field sieve is an algorithm to factor integers of the form r e − s for small positive r and |s|. The algorithm depends on arithmetic in an algebraic number field. We describe the algorithm, discuss several aspects of its implementation, and present some of the factorizations obtained. A heuristic run time analysis indicates that the number field sieve is asymptotically substantially faster than any other known factoring method, for the integers that it applies to. The number field sieve can be modified to handle arbitrary integers. This variant is slower, but asymptotically it is still expected to beat all older factoring methods.

The second author was supported by NSF under Grant No. DMS-9002939 and by NSA/MSP under Grant No. MDA90-H-4043.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 34.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 44.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. L.M. Adleman, Factoring numbers using singular integers, Proc. 23rd Annual ACM Symp. on Theory of Computing (STOC), New Orleans, May 6–8, 1991, 64–71.

    Google Scholar 

  2. D. J. Bernstein, A. K. Lenstra, A general number field sieve implementation, this volume, pp. 103–126.

    Google Scholar 

  3. J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, S. S. Wagstaff, Jr., Factorizations of b n ± 1, b=2, 3, 5, 6, 7, 10, 11, 12 up to high powers, second edition, Contemp. Math. 22, Amer. Math. Soc., Providence, 1988.

    MATH  Google Scholar 

  4. J. Buchmann, Complexity of algorithms in algebraic number theory, in: R. A. Mollin (ed.), Proceedings of the first conference of the Canadian Number Theory Association, De Gruyter, Berlin, 1990, 37–53.

    Google Scholar 

  5. J. Buchmann, H. W. Lenstra, Jr., Approximating rings of integers in number fields, in preparation.

    Google Scholar 

  6. J. Buchmann, V. Shoup, Constructing nonresidues in finite fields and the extended Riemann hypothesis, in preparation. Extended abstract: Proc. 23rd Annual ACM Symp. on Theory of Computing (STOC), New Orleans, May 6–8, 1991, 72–79.

    Google Scholar 

  7. J. P. Buhler, H. W. Lenstra, Jr., C. Pomerance, Factoring integers with the number field sieve, this volume, pp. 50–94.

    Google Scholar 

  8. H. Cohen, A course in computational algebraic number theory, Springer-Verlag, to appear.

    Google Scholar 

  9. H. Cohen, H. W. Lenstra, Jr., Heuristics on class groups, pp. 33–62 in: H. Jager (ed.), Number theory, Noordwijkerhout 1983, Lecture Notes in Math. 1068, Springer-Verlag, Heidelberg.

    Google Scholar 

  10. D. Coppersmith, Fast evaluations of logarithms in fields of characteristic 2, IEEE Trans. Inform. Theory 30 (1984), 587–594.

    Article  MathSciNet  MATH  Google Scholar 

  11. D. Coppersmith, Modifications to the number field sieve, J. Cryptology, to appear; IBM Research Report RC 16264, 1990.

    Google Scholar 

  12. D. Coppersmith, Solving linear equations over GF(2): block Lanczos algorithm, Linear Algebra Appl., to appear; IBM Research Report RC 16997, 1991.

    Google Scholar 

  13. D. Coppersmith, Solving linear equations over GF(2) II: block Wiedemann algorithm, Math. Comp., to appear; IBM Research Report RC 17293, 1991.

    Google Scholar 

  14. D. Coppersmith, A. M. Odlyzko, R. Schroeppel, Discrete logarithms in GF(p), Algorithmica 1 (1986), 1–15.

    Article  MathSciNet  MATH  Google Scholar 

  15. J.-M. Couveignes, Computing a square root for the number field sieve, this volume, pp. 95–102.

    Google Scholar 

  16. J. D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), 255–260.

    Article  MathSciNet  MATH  Google Scholar 

  17. T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over GF(p 2), IEEE Trans. Inform. Theory 31 (1985), 473–481.

    Article  MathSciNet  MATH  Google Scholar 

  18. D. M. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAM J. Discrete Math. 6 (1993), 124–138.

    Article  MathSciNet  MATH  Google Scholar 

  19. D. M. Gordon, K. S. McCurley, Massively parallel computation of discrete logarithms, Advances in cryptology, Crypto '92, to appear.

    Google Scholar 

  20. J. L. Hafner, K. S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 1068–1083.

    Article  MathSciNet  MATH  Google Scholar 

  21. D. E. Knuth, The art of computer programming, volume 2, Seminumerical algorithms, second edition, Addison-Wesley, Reading, Massachusetts, 1981.

    MATH  Google Scholar 

  22. B. A. LaMacchia, A. M. Odlyzko, Solving large sparse systems over finite fields, Advances in cryptology, Crypto '90, Lecture Notes in Comput. Sci. 537 (1991), 99–129.

    MATH  Google Scholar 

  23. B. A. LaMacchia, A. M. Odlyzko, Computation of discrete logarithms in prime fields, Designs, Codes and Cryptography 1 (1991), 47–62.

    Article  MathSciNet  MATH  Google Scholar 

  24. S. Lang, Algebra, third edition, Addison-Wesley, Reading, Massachusetts, 1993.

    MATH  Google Scholar 

  25. A. K. Lenstra, H. W. Lenstra, Jr., Algorithms in number theory, Chapter 12 in: J. van Leeuwen (ed.), Handbook of theoretical computer science, Volume A, Algorithms and complexity, Elsevier, Amsterdam, 1990.

    Google Scholar 

  26. A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), to appear.

    Google Scholar 

  27. A. K. Lenstra, M. S. Manasse, Factoring by electronic mail, Advances in cryptology, Eurocrypt '89, Lecture Notes in Comput. Sci. 434 (1990), 355–371.

    Article  MathSciNet  Google Scholar 

  28. A. K. Lenstra, M. S. Manasse, Factoring with two large primes, Math. Comp., to appear.

    Google Scholar 

  29. H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649–673.

    Article  MathSciNet  MATH  Google Scholar 

  30. H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211–244.

    Article  MathSciNet  MATH  Google Scholar 

  31. H. W. Lenstra, Jr., C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483–516.

    Article  MathSciNet  MATH  Google Scholar 

  32. M. A. Morrison, J. Brillhart, A method of factoring and the factorization of F 7, Math. Comp. 29 (1975), 183–205.

    MathSciNet  MATH  Google Scholar 

  33. M. Pohst, H. Zassenhaus, Algorithmic algebraic number theory, Cambridge University Press, Cambridge, 1989.

    Book  MATH  Google Scholar 

  34. C. Pomerance, Analysis and comparison of some integer factoring algorithms, pp. 89–139 in: H. W. Lenstra, Jr., R. Tijdeman (eds), Computational methods in number theory, Math. Centre Tracts 154/155, Mathematisch Centrum, Amsterdam, 1983.

    Google Scholar 

  35. C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, in: D. S. Johnson, T. Nishizeki, A. Nozaki, H. S. Wilf (eds), Discrete algorithms and complexity, Academic Press, Orlando, 1987, 119–143.

    Google Scholar 

  36. C. Pomerance (ed.), Cryptology and computational number theory, Proc. Sympos. Appl. Math. 42, Amer. Math. Soc., Providence, 1990.

    MATH  Google Scholar 

  37. C. Pomerance, J. W. Smith, Reduction of huge, sparse matrices over finite fields via created catastrophes, Experiment. Math. 1 (1992), 89–94.

    Article  MathSciNet  MATH  Google Scholar 

  38. C. P. Schnorr, Refined analysis and improvements on some factoring algorithms, J. Algorithms 3 (1982), 101–127.

    Article  MathSciNet  MATH  Google Scholar 

  39. O. Schirokauer, On pro-finite groups and on discrete logarithms, Ph.D. thesis, University of California, Berkeley, 68 pages, May 1992.

    Google Scholar 

  40. I. N. Stewart, D. O. Tall, Algebraic number theory, second edition, Chapman and Hall, London, 1987.

    MATH  Google Scholar 

  41. B. Vallée, Generation of elements with small modular squares and provably fast integer factoring algorithms, Math. Comp. 56 (1991), 823–849.

    Article  MathSciNet  MATH  Google Scholar 

  42. D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), 54–62.

    Article  MathSciNet  MATH  Google Scholar 

  43. H. G. Zimmer, Computational problems, methods and results in algebraic number theory, Lecture Notes in Math. 262, Springer-Verlag, Berlin, 1972.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Room MRE-2Q334, Bellcore, 445 South Street, 07960, Morristown, NJ, USA

    A. K. Lenstra

  2. Department of Mathematics, University of California, 94720, Berkeley, CA, USA

    H. W. Lenstra Jr.

  3. DEC SRC, 130 Lytton Avenue, 94301, Palo Alto, CA, USA

    M. S. Manasse

  4. Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, RG8 8EX, Reading, Berkshire, England

    J. M. Pollard

Authors
  1. A. K. Lenstra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. W. Lenstra Jr.
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. S. Manasse
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. J. M. Pollard
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Arjen K. Lenstra Hendrik W. Lenstra Jr.

Rights and permissions

Reprints and permissions

Copyright information

© 1993 Springer-Verlag

About this paper

Cite this paper

Lenstra, A.K., Lenstra, H.W., Manasse, M.S., Pollard, J.M. (1993). The number field sieve. In: Lenstra, A.K., Lenstra, H.W. (eds) The development of the number field sieve. Lecture Notes in Mathematics, vol 1554. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0091537

Download citation

  • DOI: https://doi.org/10.1007/BFb0091537

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-57013-4

  • Online ISBN: 978-3-540-47892-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation