Abstract
The year 2013 has seen several major complexity advances for the discrete logarithm problem in multiplicative groups of small- characteristic finite fields. These outmatch, asymptotically, the Function Field Sieve (FFS) approach, which was so far the most efficient algorithm known for this task. Yet, on the practical side, it is not clear whether the new algorithms are uniformly better than FFS. This article presents the state of the art with regard to the FFS algorithm, and reports data from a record-sized discrete logarithm computation in a prime-degree extension field.
Chapter PDF
Similar content being viewed by others
References
Adj, G., Menezes, A., Oliveira, T., Rodríguez-Henríquez, F.: Weakness of \(\mathbb{F}_{3^{6*509}}\) for discrete logarithm cryptography, preprint, 24 pages (2013), http://eprint.iacr.org/2013/446
Adleman, L.M.: The function field sieve. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, pp. 108–121. Springer, Heidelberg (1994)
Adleman, L.M., Huang, M.D.A.: Function field sieve method for discrete logarithms over finite fields. Inf. Comput. 151(1-2), 5–16 (1999)
Aoki, K., Franke, J., Kleinjung, T., Lenstra, A.K., Osvik, D.A.: A kilobit special number field sieve factorization. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 1–12. Springer, Heidelberg (2007)
Bai, S., Bouvier, C., Filbois, A., Gaudry, P., Imbert, L., Kruppa, A., Morain, F., Thomé, E., Zimmermann, P.: CADO-NFS, an implementation of the number field sieve algorithm (2013), development version http://cado-nfs.gforge.inria.fr/
Bai, S., Filbois, A., Gaudry, P., Kruppa, A., Morain, F., Thomé, E., Zimmermann, P.: CADO-NFS, Crible Algébrique: Distribution, Optimisation - Number Field Sieve, http://cado-nfs.gforge.inria.fr/
Barbulescu, R.: Selecting polynomials for the Function Field Sieve. 23 pages (2013), http://hal.inria.fr/hal-00798386 (preprint)
Barbulescu, R., Bouvier, C., Detrey, J., Gaudry, P., Jeljeli, H., Thomé, E., Videau, M., Zimmermann, P.: The relationship between some guy and cryptography, ECC 2012, rump session talk (humoristic) (2012), http://ecc.rump.cr.yp.to/
Barbulescu, R., Gaudry, P., Joux, A., Thomé, E.: A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, 8 pages (2013), http://hal.inria.fr/hal-00835446 (preprint)
Bouvier, C.: The filtering step of discrete logarithm and integer factorization algorithms, 22 pages (2013), http://hal.inria.fr/hal-00734654 (preprint)
Detrey, J., Gaudry, P., Videau, M.: Relation collection for the Function Field Sieve. In: Nannarelli, A., Seidel, P.M., Tang, P.T.P. (eds.) Proceedings of ARITH-21, pp. 201–210. IEEE (2013)
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory 22(6), 644–654 (1976)
ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31(4), 469–472 (1985)
Granger, R., Holt, A.J., Page, D.L., Smart, N.P., Vercauteren, F.: Function field sieve in characteristic three. In: Buell, D.A. (ed.) ANTS 2004. LNCS, vol. 3076, pp. 223–234. Springer, Heidelberg (2004)
Hayashi, T., Shimoyama, T., Shinohara, N., Takagi, T.: Breaking pairing-based cryptosystems using η T pairing over GF(397). In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 43–60. 7658, Heidelberg (2012)
Jeljeli, H.: Accelerating iterative SpMV for Discrete Logarithm Problem using GPUs, 11 pages (2013), http://hal.inria.fr/hal-00734975 (preprint)
Joux, A., Lercier, R.: Discrete logarithms in GF(2n) (521 bits), email to the NMBRTHRY mailing list (September 2001), http://listserv.nodak.edu/archives/nmbrthry.html
Joux, A., Lercier, R.: The function field sieve is quite special. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp. 431–445. Springer, Heidelberg (2002)
Joux, A.: A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic, To appear in Selected Areas in Cryptography, 12 pages (2013), http://eprint.iacr.org/2013/095 (preprint)
Joux, A., Lercier, R.: Improvements to the general number field sieve for discrete logarithms in prime fields. A Comparison with the Gaussian Integer Method 72(242), 953–967 (2003)
Joux, A., Lercier, R.: Discrete logarithms in GF(2607) and GF(2613). E-mail to the NMBRTHRY mailing list (September 2005), http://listserv.nodak.edu/archives/nmbrthry.html
Kaltofen, E.: Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems. Mathematics of Computation 64(210), 777–806 (1995)
Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., te Riele, H., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010)
Lenstra, A.K., Kleinjung, T., Thomé, E.: Universal security. In: Fischlin, M., Katzenbeisser, S. (eds.) Buchmann Festschrift. LNCS, vol. 8260, pp. 121–124. Springer, Heidelberg (2013)
Matsumoto, R.: Using C ab curves in the function field sieve. IEICE Trans. Fund. E82-A(3), 551–552 (1999)
Murphy, B.A.: Polynomial selection for the number field sieve integer factorisation algorithm. Phd thesis, Australian National University (1999)
National Institute of Standards and Technology: Digital signature standard, DSS (2013), http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 International Association for Cryptologic Research
About this paper
Cite this paper
Barbulescu, R. et al. (2014). Discrete Logarithm in GF(2809) with FFS. In: Krawczyk, H. (eds) Public-Key Cryptography – PKC 2014. PKC 2014. Lecture Notes in Computer Science, vol 8383. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54631-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-54631-0_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54630-3
Online ISBN: 978-3-642-54631-0
eBook Packages: Computer ScienceComputer Science (R0)