Mathematics of Computation

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

Author(s): Antoine Joux; Reynald Lercier.
Journal: Math. Comp. 72 (2003), 953-967.
MSC (2000): Primary 11T99; Secondary 11Y05
Posted: November 4, 2002
Retrieve article in: PDF DVI PostScript

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.

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

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS