Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method


Authors: Antoine Joux and Reynald Lercier
Journal: Math. Comp. 72 (2003), 953-967
MSC (2000): Primary 11T99; Secondary 11Y05
DOI: https://doi.org/10.1090/S0025-5718-02-01482-5
Published electronically: November 4, 2002
MathSciNet review: 1954978
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we describe many improvements to the number field sieve. Our main contribution consists of a new way to compute individual logarithms with the number field sieve without solving a very large linear system for each logarithm. We show that, with these improvements, the number field sieve outperforms the gaussian integer method in the hundred digit range. We also illustrate our results by successfully computing discrete logarithms with GNFS in a large prime field.


References [Enhancements On Off] (What's this?)

  • 1. L.M. Adleman, Factoring numbers using singular integers, Proceedings 23rd Annual ACM Symposium on Theory of Computing (STOC), 1991, pp. 64-71.
  • 2. D. Atkins, M. Graff, A. K. Lenstra, and P. C. Leyland, The magic words are squeamish ossifrage, Advances in Cryptology -- ASIACRYPT'94, Lecture Notes in Computer Science, vol. 917, Springer-Verlag, 1995, pp. 265-277. MR 97b:94019
  • 3. D. J. Bernstein and A.K. Lenstra, A general number field sieve implementation, Springer-Verlag, 1993, pp. 103-126. CMP 95:09
  • 4. J. Buchmann, J. Loho, and J. Zayer, An implementation of the general number field sieve, Advances in Cryptology -- CRYPTO'93, Lecture Notes in Computer Science, vol. 773, 1994, pp. 159-165. MR 95e:11132
  • 5. J.P. Buhler, Jr. H.W. Lenstra, and Carl Pomerance, Factoring integer with the number field sieve, Springer-Verlag, 1993, pp. 50-94 (see [26]). CMP 95:09
  • 6. S. Cavallar, Strategies in filtering in the number field sieve, Proceedings of the ANTS-IV conference (W. Bosma, ed.), Lecture Notes in Computer Science, vol. 1838, Springer-Verlag, 2000, pp. 209-231. MR 2002h:11139
  • 7. S. Cavallar, B. Dodson, A.K. Lenstra, W. Lioen, , P.L. Montgomery, B. Murphy, H. te Riele, K. Aardal, J. Gilchrist, G. Guillerm, P. Leyland, J. Marchand, F. Morain, A. Muffet, C. Putman, C. Putman, and P. Zimmerman, Factorization of a 512-bit RSA modulus, Advances in Cryptology -- EUROCRYPT'2000 (B. Preneel, ed.), Lecture Notes in Computer Science, vol. 1807, Springer-Verlag, 2000, pp. 1-18.
  • 8. Stefania Cavallar, Bruce Dodson, Arjen Lenstra, Paul Leyland, Walter Lioen, Peter Mongomery, Brian Murphy, Herman te Riele, and Paul Zimmerman, Factorization of RSA-140, http://listserv.nodak.edu/archives/nmbrthry.html -- February, 1999.
  • 9. D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE transactions on information theory IT-30 (1984), no. 4, 587-594. MR 85h:65041
  • 10. D. Coppersmith, A. Odlyzko, and R. Schroppel, Discrete logarithms in ${\mathbb F}_{p}$, Algorithmica 1 (1986), 1-15. MR 87g:11167
  • 11. J.-M. Couveignes, Computing a square root for the number field sieve, Springer-Verlag, 1993, pp. 95-102 (see [26]). CMP 95:09
  • 12. J. Cowie, B. Dodson, R. M. Elkenbracht-Huizing, A. K. Lenstra, P. L. Montgomery, and J. Zayer, A world wide number field sieve factoring record: On to 512 bits, Advances in Cryptology -- ASIACRYPT'96 (K. Kim and T. Matsumoto, eds.), Lecture Notes in Computer Science, vol. 1163, Springer-Verlag, 1996, pp. 382-394. CMP 98:05
  • 13. Th. Denny and V. Müller, On the reduction of composed relations from the number field sieve, Proceedings of the ANTS-II conference (H. Cohen, ed.), Lecture Notes in Computer Science, vol. 1122, Springer-Verlag, 1996, pp. 75-90. MR 98k:11184
  • 14. B. Dodson and A. K. Lenstra, NFS with four large primes: an explosive experiment, Advances in Cryptology -- CRYPTO'95, Lecture Notes in Computer Science, vol. 963, Springer-Verlag, 1995, pp. 372-385. MR 98d:11156
  • 15. R. M. Elkenbracht-Huizing, P. Montgomery, R. Silverman, R. K. Wackerbarth, and Jr. S. S. Wagstaff, The number field sieve on many computers, Fifth Conference of the Canadian Number Theory Association (Providence RI), CRM Proc. Lecture Notes, no. 19, Amer. Math. Soc., 1999. MR 2000e:11157
  • 16. R.M. Elkenbracht-Huizing, An implementation of the number field sieve, Tech. Report NM-R9511, CWI, 1995. Experiment. Math. 5 (1996), 231-253. MR 98a:11182
  • 17. -, A multiple polynomial general number field sieve, Proceedings of the ANTS-II conference (H. Cohen, ed.), Lecture Notes in Computer Science, vol. 1122, Springer-Verlag, 1996. MR 98g:11142
  • 18. R. Golliver, A. K. Lenstra, and K. McCurley, Lattice sieving and trial division, Proceedings of the ANTS-I conference, Lecture Notes in Computer Science, vol. 877, Springer-Verlag, 1994, pp. 18-27. MR 96a:11142
  • 19. D. Gordon, Discrete logarithms in ${\mathbb F}_{p}$ using the number field sieve, SIAM J. Discrete Math 6 (1993), 124-138. MR 94d:11104
  • 20. D. Gordon and K. McCurley, Massively parallel computation of discrete logarithms, Advances in Cryptology -- CRYPTO'92, Lecture Notes in Computer Science, vol. 740, Springer-Verlag, 1993, pp. 312-323.
  • 21. A. Joux, La réduction de réseaux en cryptographie, Ph.D. thesis, Ecole Polytechnique, Palaiseau, France, 1993.
  • 22. A. Joux and J. Stern, Lattice reduction: A toolbox for the cryptanalyst, J. Cryptology 11 (1998), 161-185. MR 99c:94031
  • 23. Antoine Joux and Reynald Lercier, Discrete logarithms in GF(p), http://listserv.nodak.edu/archives/nmbrthry.html -- May, 1998.
  • 24. B. A. LaMacchia and A. M. Odlyzko, Computation of discrete logarithms in prime fields, Designs, Codes and Cryptography 1 (1991), 47-62. MR 92j:11148
  • 25. -, Solving large sparse linear systems over finite fields, Advances in Cryptology -- CRYPTO'90, Lecture Notes in Computer Science, vol. 537, Springer-Verlag, 1991, pp. 109-133.
  • 26. A. K. Lenstra and H. W. Lenstra, Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, 1993. MR 96m:11116
  • 27. A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Ann. 261 (1982), 513-534. MR 84a:12002
  • 28. A.K. Lenstra, Jr. H.W. Lenstra, M.S. Manasse, and J.M. Pollard, The factorization of the ninth fermat number, Math. Comp. 61 (1993). MR 93k:11116
  • 29. -, The number field sieve, Springer-Verlag, 1993, pp. 11-42 (see [26]). CMP 95:09
  • 30. K. McCurley, The discrete logarithm problem, Proc. Symp. in Applied Mathematics, Cryptology and Computational Number Theory, no. 42, 1990, pp. 49-74.MR 92d:11133
  • 31. P. L. Montgomery, A block Lanczos algorithm for finding dependencies over ${\mathbb F}_{2}$, Advances in Cryptology -- EUROCRYP'95, Lecture Notes in Computer Science, vol. 921, Springer-Verlag, 1995, pp. 106-120. MR 97c:11115
  • 32. A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in Cryptology -- EUROCRYP'84 (T. Beth, N. Cot, and I. Ingemarsson, eds.), Lecture Notes in Computer Science, vol. 209, Springer-Verlag, 1985, pp. 224-314. MR 87g:11022
  • 33. J.M. Pollard, Factoring with cubic integer, Springer-Verlag, 1993, pp. 4-10 (see [26]). CMP 95:09
  • 34. -, The lattice sieve, Springer-Verlag, 1993, pp. 43-49. CMP 95:09
  • 35. O. Schirokauer, Discrete logarithms and local units, Phil. Trans. R. Soc. Lond. A 345 (1993), 409-423. MR 95c:11156
  • 36. O. Schirokauer, D. Weber, and Th. Denny, Discrete logarithms: the effectiveness of the index calculus method, Proceedings of the ANTS-II conference (H. Cohen, ed.), Lecture Notes in Computer Science, vol. 1122, Springer-Verlag, 1996. MR 98i:11109
  • 37. RSA Data Security, The RSA factoring challenge, http://www.rsa.com/rsalabs/html/factoring.html.
  • 38. R. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), 329-340. MR 88c:11079
  • 39. F. Valette, Algèbre linéaire pour le logarithme discret, Master's thesis, ENSTA, 1999, Stage de fin d'étude et de DEA.
  • 40. D. Weber, Computing discrete logarithms with the number field sieve, Proceedings of the ANTS-II conference, Lecture Notes in Computer Science, vol. 1122, Springer-Verlag, 1996. MR 98k:11186
  • 41. -, Computing discrete logarithms with quadratic number rings, Advances in Cryptology -- EUROCRYP'98 (K. Nyberg, ed.), Lecture Notes in Computer Science, vol. 1403, Springer-Verlag, 1998, pp. 171-183. CMP 2000:07
  • 42. D. Weber and Th. Denny, The solution of McCurley's discrete log challenge, Advances in Cryptology -- CRYPTO'98 (H. Krawczyk, ed.), Lecture Notes in Computer Science, vol. 1462, Springer-Verlag, 1998, pp. 458-471. MR 99i:94057

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11T99, 11Y05

Retrieve articles in all journals with MSC (2000): 11T99, 11Y05


Additional Information

Antoine Joux
Affiliation: DCSSI, 18 rue du Dr. Zamenhoff, F-92131 Issy-les-Moulineaux, France
Email: Antoine.Joux@m4x.org

Reynald Lercier
Affiliation: CELAR, Route de Laillé, F-35998 Rennes Armées, France
Email: lercier@celar.fr

DOI: https://doi.org/10.1090/S0025-5718-02-01482-5
Received by editor(s): July 27, 1999
Received by editor(s) in revised form: October 18, 2000
Published electronically: November 4, 2002
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society