link.springer.com

The number field sieve

  • ️Sun Jan 01 2006

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

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