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

Joux, Antoine; Lercier, Reynald

doi:10.1090/S0025-5718-02-01482-5

Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
HTML articles powered by AMS MathViewer

by Antoine Joux and Reynald Lercier PDF

Math. Comp. 72 (2003), 953-967 Request permission

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

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 10.1007/3-540-48329-2_{1}4
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 10.1007/10722028_{1}1
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 10.1109/TIT.1984.1056941
Don Coppersmith, Andrew M. Odlzyko, and Richard Schroeppel, Discrete logarithms in $\textrm {GF}(p)$, Algorithmica 1 (1986), no. 1, 1–15. MR 833115, DOI 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 10.1007/3-540-61581-4_{4}3
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 10.1007/3-540-44750-4_{3}0
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 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, DOI 10.1080/10586458.1996.10504590
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 10.1007/3-540-61581-4_{4}5
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 10.1007/3-540-58691-1_{3}8
Daniel M. Gordon, Discrete logarithms in $\textrm {GF}(p)$ using the number field sieve, SIAM J. Discrete Math. 6 (1993), no. 1, 124–138. MR 1201995, DOI 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 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 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, DOI 10.1007/BFb0091534
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 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 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 10.1090/psapm/042/1095551
Peter L. Montgomery, A block Lanczos algorithm for finding dependencies over $\textrm {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 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 10.1007/3-540-39757-4_{2}0
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 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 10.1007/3-540-61581-4_{6}6
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 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 10.1007/3-540-61581-4_{7}0
—, 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 10.1007/BFb0055747