Abstract
The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF(\(p^n\)) where \(n\) is a small integer greater than \(1\). Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good polynomials that define the extension fields used in NFS. We design two new methods for this task, modifying the asymptotic complexity and paving the way for record-breaking computations. We exemplify these results with the computation of discrete logarithms over a field GF(\(p^2\)) whose cardinality is 180 digits (595 bits) long.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bai, S., Filbois, A., Gaudry, P., Kruppa, A., Morain, F., Thomé, E., Zimmermann, P., et al.: Crible algébrique: Distribution, optimisation - NFS (2009). downloadable at http://cado-nfs.gforge.inria.fr/
Barbulescu, R., Gaudry, P., Joux, A., Thomé, E.: A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 1–16. Springer, Heidelberg (2014)
Barbulescu, R., Pierrot, C.: The multiple number field sieve for medium- and high-characteristic finite fields. LMS Journal of Computation and Mathematics 17, 230–246 (2014). http://journals.cambridge.org/article_S1461157014000369
Barbulescu, R.: Algorithmes de logarithmes discrets dans les corps finis. Ph.D. thesis, Université de Lorraine (2013)
Barbulescu, R., Gaudry, P., Guillevic, A., Morain, F.: Improvements to the number field sieve for non-prime finite fields. preprint available at http://hal.inria.fr/hal-01052449
Bouvier, C., Gaudry, P., Imbert, L., Jeljeli, H., Thomé, E.: Discrete logarithms in GF(p) – 180 digits (2014), announcement available at the NMBRTHRY archives, item 004703
Canfield, E.R., Erdös, P., Pomerance, C.: On a problem of Oppenheim concerning “factorisatio numerorum”. J. Number Theory 17(1), 1–28 (1983)
Collins, G.E., Encarnación, M.J.: Efficient rational number reconstruction. Journal of Symbolic Computation 20(3), 287–297 (1995)
Coppersmith, D.: Modifications to the number field sieve. J. of Cryptology 6(3), 169–180 (1993)
Coppersmith, D.: Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Math. Comp. 62(205), 333–350 (1994)
Foster, K.: HT90 and “simplest” number fields. Illinois J. Math. 55(4), 1621–1655 (2011)
Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. of Cryptology 23(2), 224–280 (2010)
Jeljeli, H.: Accelerating iterative SpMV for discrete logarithm problem using GPUs (2014). http://hal.inria.fr/hal-00734975/, preprint, to appear in WAIFI 2014
Jeljeli, H.: An implementation of the Block-Wiedemann algorithm on NVIDIA-GPUs using the Residue Number System (RNS) arithmetic (2014). available from http://www.loria.fr/~hjeljeli/
Joux, A., Lercier, R.: Improvements to the general number field for discrete logarithms in prime fields. Math. Comp. 72(242), 953–967 (2003)
Joux, A., Lercier, R., Smart, N.P., Vercauteren, F.: The Number Field Sieve in the Medium Prime Case. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 326–344. Springer, Heidelberg (2006)
Joux, A., Lercier, R., et al.: Algorithmes pour résoudre le problème du logarithme discret dans les corps finis. Nouvelles Méthodes Mathématiques en Cryptographie, volume Fascicule Journées Annuelles, p. 23 (2007)
Joux, A., Pierrot, C.: The Special Number Field Sieve in \(\mathbb{F}_{p^{n}}\). In: Cao, Z., Zhang, F. (eds.) Pairing 2013. LNCS, vol. 8365, pp. 45–61. Springer, Heidelberg (2014)
Kalkbrener, M.: An upper bound on the number of monomials in determinants of sparse matrices with symbolic entries. Mathematica Pannonica 73, 82 (1997)
Kleinjung, T.: On polynomial selection for the general number field sieve. Mathematics of Computation 75(256), 2037–2047 (2006)
Lenstra, A.K., Verheul, E.R.: The XTR Public Key System. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 1–19. Springer, Heidelberg (2000)
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515–534 (1982)
Matyukhin, D.V.: On asymptotic complexity of computing discrete logarithms over GF(p). Discrete Mathematics and Applications 13(1), 27–50 (2003)
Matyukhin, D.: Effective version of the number field sieve for discrete logarithms in the field GF\((p^k)\). Trudy po Discretnoi Matematike 9, 121–151 (2006) (in Russian). http://m.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tdm&paperid=144&option_lang=eng
Murphy, B.A.: Polynomial selection for the number field sieve integer factorisation algorithm. Ph.D. thesis, Australian National Univers (1999)
Pierrot, C.: The multiple number field sieve with conjugation method (August 2014). preprint available at https://eprint.iacr.org/2014/641
Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF(p) and his cryptographic significance. IEEE Trans. Inform. Theory 24(1), 106–110 (1978)
Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comp. 32(143), 918–924 (1978)
Rubin, K., Silverberg, A.: Torus-Based Cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 349–365. Springer, Heidelberg (2003)
Schirokauer, O.: Using number fields to compute logarithms in finite fields. Math. Comp. 69(231), 1267–1283 (2000)
Schirokauer, O.: Virtual logarithms. J. Algorithms 57, 140–147 (2005)
Smith, P., Skinner, C.: A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms. In: Pieprzyk, J., Safavi-Naini, R. (eds.) Advances in Cryptology - ASIACRYPT 1994. LNCS, vol. 917, pp. 357–364. Springer, Heidelberg (1994)
Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Trans. Inform. Theory 32(1), 54–62 (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Barbulescu, R., Gaudry, P., Guillevic, A., Morain, F. (2015). Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields. In: Oswald, E., Fischlin, M. (eds) Advances in Cryptology -- EUROCRYPT 2015. EUROCRYPT 2015. Lecture Notes in Computer Science(), vol 9056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46800-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-662-46800-5_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46799-2
Online ISBN: 978-3-662-46800-5
eBook Packages: Computer ScienceComputer Science (R0)