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.
- L.M. Adleman, Factoring numbers using singular integers, Proceedings 23rd Annual ACM Symposium on Theory of Computing (STOC), 1991, pp. 64–71.
- Derek Atkins, Michael Graff, Arjen K. Lenstra, and Paul C. Leyland, The magic words are squeamish ossifrage (extended abstract), Advances in cryptology—ASIACRYPT ’94 (Wollongong, 1994) Lecture Notes in Comput. Sci., vol. 917, Springer, Berlin, 1995, pp. 263–277. MR 1376383
- D. J. Bernstein and A.K. Lenstra, A general number field sieve implementation, Springer–Verlag, 1993, pp. 103–126.
- J. Buchmann, J. Loho, and J. Zayer, An implementation of the general number field sieve (extended abstract), Advances in cryptology—CRYPTO ’93 (Santa Barbara, CA, 1993) Lecture Notes in Comput. Sci., vol. 773, Springer, Berlin, 1994, pp. 159–165. MR 1288967, DOI https://doi.org/10.1007/3-540-48329-2_14
- 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]).
- Stefania Cavallar, Strategies in filtering in the number field sieve, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 209–231. MR 1850607, DOI https://doi.org/10.1007/10722028_11
- 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.
- 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.
- Don Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory 30 (1984), no. 4, 587–594. MR 755785, DOI https://doi.org/10.1109/TIT.1984.1056941
- Don Coppersmith, Andrew M. Odlzyko, and Richard Schroeppel, Discrete logarithms in ${\rm GF}(p)$, Algorithmica 1 (1986), no. 1, 1–15. MR 833115, DOI https://doi.org/10.1007/BF01840433
- J.-M. Couveignes, Computing a square root for the number field sieve, Springer–Verlag, 1993, pp. 95–102 (see [26]).
- 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.
- Thomas F. Denny and Volker Müller, On the reduction of composed relations from the number field sieve, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 75–90. MR 1446500, DOI https://doi.org/10.1007/3-540-61581-4_43
- Bruce Dodson and Arjen K. Lenstra, NFS with four large primes: an explosive experiment, Advances in cryptology—CRYPTO ’95 (Santa Barbara, CA, 1995) Lecture Notes in Comput. Sci., vol. 963, Springer, Berlin, 1995, pp. 372–385. MR 1445575, DOI https://doi.org/10.1007/3-540-44750-4_30
- R.-M. Elkenbracht-Huizing, Peter L. Montgomery, R. D. Silverman, R. K. Wackerbarth, and S. S. Wagstaff Jr., The number field sieve on many computers, Number theory (Ottawa, ON, 1996) CRM Proc. Lecture Notes, vol. 19, Amer. Math. Soc., Providence, RI, 1999, pp. 81–85. MR 1684593, DOI https://doi.org/10.1090/crmp/019/09
- Marije Elkenbracht-Huizing, An implementation of the number field sieve, Experiment. Math. 5 (1996), no. 3, 231–253. MR 1426450
- Marije Elkenbracht-Huizing, A multiple polynomial general number field sieve, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 99–114. MR 1446502, DOI https://doi.org/10.1007/3-540-61581-4_45
- Roger A. Golliver, Arjen K. Lenstra, and Kevin S. McCurley, Lattice sieving and trial division, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 18–27. MR 1322707, DOI https://doi.org/10.1007/3-540-58691-1_38
- Daniel M. Gordon, Discrete logarithms in ${\rm GF}(p)$ using the number field sieve, SIAM J. Discrete Math. 6 (1993), no. 1, 124–138. MR 1201995, DOI https://doi.org/10.1137/0406010
- 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.
- A. Joux, La réduction de réseaux en cryptographie, Ph.D. thesis, Ecole Polytechnique, Palaiseau, France, 1993.
- Antoine Joux and Jacques Stern, Lattice reduction: a toolbox for the cryptanalyst, J. Cryptology 11 (1998), no. 3, 161–185. MR 1633944, DOI https://doi.org/10.1007/s001459900042
- Antoine Joux and Reynald Lercier, Discrete logarithms in GF(p), http://listserv.nodak.edu/archives/nmbrthry.html — May, 1998.
- B. A. LaMacchia and A. M. Odlyzko, Computation of discrete logarithms in prime fields, Des. Codes Cryptogr. 1 (1991), no. 1, 47–62. MR 1110012, DOI https://doi.org/10.1007/BF00123958
- ---, 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.
- A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI https://doi.org/10.1007/BF01457454
- A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), no. 203, 319–349. MR 1182953, DOI https://doi.org/10.1090/S0025-5718-1993-1182953-4
- ---, The number field sieve, Springer–Verlag, 1993, pp. 11–42 (see [26]).
- Kevin S. McCurley, The discrete logarithm problem, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 49–74. MR 1095551, DOI https://doi.org/10.1090/psapm/042/1095551
- Peter L. Montgomery, A block Lanczos algorithm for finding dependencies over ${\rm GF}(2)$, Advances in cryptology—EUROCRYPT ’95 (Saint-Malo, 1995) Lecture Notes in Comput. Sci., vol. 921, Springer, Berlin, 1995, pp. 106–120. MR 1367513, DOI https://doi.org/10.1007/3-540-49264-X_9
- A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 224–314. MR 825593, DOI https://doi.org/10.1007/3-540-39757-4_20
- J.M. Pollard, Factoring with cubic integer, Springer–Verlag, 1993, pp. 4–10 (see [26]).
- ---, The lattice sieve, Springer–Verlag, 1993, pp. 43–49.
- Oliver Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A 345 (1993), no. 1676, 409–423. MR 1253502, DOI https://doi.org/10.1098/rsta.1993.0139
- Oliver Schirokauer, Damian Weber, and Thomas Denny, Discrete logarithms: the effectiveness of the index calculus method, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 337–361. MR 1446523, DOI https://doi.org/10.1007/3-540-61581-4_66
- RSA Data Security, The RSA factoring challenge, http://www.rsa.com/rsalabs/html/factoring.html.
- Robert D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329–339. MR 866119, DOI https://doi.org/10.1090/S0025-5718-1987-0866119-8
- F. Valette, Algèbre linéaire pour le logarithme discret, Master’s thesis, ENSTA, 1999, Stage de fin d’étude et de DEA.
- Damian Weber, Computing discrete logarithms with the general number field sieve, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 391–403. MR 1446527, DOI https://doi.org/10.1007/3-540-61581-4_70
- ---, 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.
- Damian Weber and Thomas Denny, The solution of McCurley’s discrete log challenge, Advances in cryptology—CRYPTO ’98 (Santa Barbara, CA, 1998) Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 458–471. MR 1670968, DOI https://doi.org/10.1007/BFb0055747
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
MR Author ID:
316495
Email:
Antoine.Joux@m4x.org
Reynald Lercier
Affiliation:
CELAR, Route de Laillé, F-35998 Rennes Armées, France
MR Author ID:
602270
ORCID:
0000-0002-0531-8945
Email:
lercier@celar.fr
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