Selecting polynomials for the Function Field Sieve
HTML articles powered by AMS MathViewer
- by Razvan Barbulescu PDF
- Math. Comp. 84 (2015), 2987-3012 Request permission
Abstract:
The Function Field Sieve algorithm is dedicated to computing discrete logarithms in a finite field $\mathbb {F}_{q^n}$, where $q$ is a small prime power. The scope of this article is to select good polynomials for this algorithm by defining and measuring the size property and the so-called root and cancellation properties. In particular we present an algorithm for rapidly testing a large set of polynomials. Our study also explains the behaviour of inseparable polynomials, in particular we give an easy way to see that the algorithm encompass the Coppersmith algorithm as a particular case.References
- Leonard M. Adleman, The function field sieve, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 108–121. MR 1322716, DOI 10.1007/3-540-58691-1_{4}8
- Leonard M. Adleman and Ming-Deh A. Huang, Function field sieve method for discrete logarithms over finite fields, Inform. and Comput. 151 (1999), no. 1-2, 5–16. MR 1692254, DOI 10.1006/inco.1998.2761
- Tom M. Apostol, Modular functions and Dirichlet series in number theory, 2nd ed., Graduate Texts in Mathematics, vol. 41, Springer-Verlag, New York, 1990. MR 1027834, DOI 10.1007/978-1-4612-0999-7
- S. Bai, Polynomial selection for the number field sieve, PhD thesis, Australian National University, 2011.
- R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau, and P. Zimmermann, The relationship between some guy and cryptography, 2012. Rump session of ECC, http://ecc.2012.rump.cr.yp.to/.
- Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
- S. Bai, A. Filbois, P. Gaudry, A. Kruppa, F. Morain, E Thomé, P. Zimmermann, Crible alébrique: Distribution, optimisation - number field sieve. http://cado-nfs.gforge.inria.fr/.
- R. Barbulescu, P. Gaudry, A. Joux, and E. Thomé, A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, http://www.springer.com/computer/security+and+cryptology/book/978-3-642-55219-9, pp. 1–16.
- 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
- J. Detrey, P. Gaudry, and M. Videau, Relation collection for the function field sieve, In IEEE Symposium on Computer Arithmetic (ARITH 21), 2013.
- F. Göloglu, R. Granger, G. McGuire, and J. Zumbrägel, On the function field sieve and the impact of higher splitting probabilities: Application to discrete logarithms in $f_{2^{1971}}$, http://www.springer.com/computer/security+and+cryptology/book/978-3-642-40083-4.
- Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157
- T. Hayashi, T. Shimoyama, N. Shinohara, and T. Takagi, Breaking pairing-based cryptosystems using $\eta _t$ pairing over $\mathrm {GF}(3^{97})$. In Advances in Cryptology – ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science, pages 43–60, 2012.
- Takuya Hayashi, Naoyuki Shinohara, Lihua Wang, Shin’ichiro Matsuo, Masaaki Shirase, and Tsuyoshi Takagi, Solving a 676-bit discrete logarithm problem in $\textrm {GF}(3^{6n})$, Public key cryptography—PKC 2010, Lecture Notes in Comput. Sci., vol. 6056, Springer, Berlin, 2010, pp. 351–367. MR 2660752, DOI 10.1007/978-3-642-13013-7_{2}1
- Kenneth Ireland and Michael Rosen, A classical introduction to modern number theory, 2nd ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990. MR 1070716, DOI 10.1007/978-1-4757-2103-4
- Antoine Joux and Reynald Lercier, The function field sieve is quite special, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 431–445. MR 2041102, DOI 10.1007/3-540-45455-1_{3}4
- Antoine Joux and Reynald Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method, Math. Comp. 72 (2003), no. 242, 953–967. MR 1954978, DOI 10.1090/S0025-5718-02-01482-5
- Antoine Joux and Reynald Lercier, The function field sieve in the medium prime case, Advances in cryptology—EUROCRYPT 2006, Lecture Notes in Comput. Sci., vol. 4004, Springer, Berlin, 2006, pp. 254–270. MR 2423547, DOI 10.1007/11761679_{1}6
- A. Joux and R. Lercier, 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, page 23, 2007.
- Antoine Joux, Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields, Advances in cryptology—EUROCRYPT 2013, Lecture Notes in Comput. Sci., vol. 7881, Springer, Heidelberg, 2013, pp. 177–193. MR 3095525, DOI 10.1007/978-3-642-38348-9_{1}1
- A. Joux, A new index calculus algorithm with complexity L$(1/4+o(1))$ in very small characteristic. Cryptology ePrint Archive, Report 2013/095, 2013. http://eprint.iacr.org/.
- Dino Lorenzini, An invitation to arithmetic geometry, Graduate Studies in Mathematics, vol. 9, American Mathematical Society, Providence, RI, 1996. MR 1376367, DOI 10.1090/gsm/009
- R. Matsumoto, Using Cab curves in the function field sieve. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 82(3):551–552, 1999.
- P.L. Montgomery, Searching for higher-degree polynomials for the general number field sieve, 2006. http://www.ipam.ucla.edu/publications/scws1/scws1_6223.ppt.
- B.A. Murphy, Polynomial selection for the number field sieve integer factorisation algorithm, PhD thesis, Australian National University, 1999.
- Jürgen Neukirch, Algebraic number theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322, Springer-Verlag, Berlin, 1999. Translated from the 1992 German original and with a note by Norbert Schappacher; With a foreword by G. Harder. MR 1697859, DOI 10.1007/978-3-662-03983-0
- Thomas Prest and Paul Zimmermann, Non-linear polynomial selection for the number field sieve, J. Symbolic Comput. 47 (2012), no. 4, 401–409. MR 2890879, DOI 10.1016/j.jsc.2011.09.004
- E. Thomé. Algorithmes de calcul des logarithmes discrets dans les corps finis, PhD thesis, École Polytechnique, Palaiseau, France, 2003.
Additional Information
- Razvan Barbulescu
- Affiliation: Université de Lorraine, CNRS, INRIA, France
- Email: razvan.barbulescu@inria.fr
- Received by editor(s): March 8, 2013
- Received by editor(s) in revised form: October 18, 2013, and February 12, 2014
- Published electronically: March 20, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 2987-3012
- MSC (2010): Primary 12Y05; Secondary 12F15
- DOI: https://doi.org/10.1090/S0025-5718-2015-02940-8
- MathSciNet review: 3378859