Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Selecting polynomials for the Function Field Sieve


Author: Razvan Barbulescu
Journal: Math. Comp. 84 (2015), 2987-3012
MSC (2010): Primary 12Y05; Secondary 12F15
DOI: https://doi.org/10.1090/S0025-5718-2015-02940-8
Published electronically: March 20, 2015
MathSciNet review: 3378859
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [Adl94] 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 (96d:11135), https://doi.org/10.1007/3-540-58691-1_48
  • [AH99] 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 (2001c:11136b), https://doi.org/10.1006/inco.1998.2761
  • [Apo90] 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 (90j:11001)
  • [Bai11] S. Bai,
    Polynomial selection for the number field sieve,
    PhD thesis, Australian National University, 2011.
  • [BBD$^+$12] 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/.
  • [BCP97] 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, https://doi.org/10.1006/jsco.1996.0125
  • [BFG$^+$] 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/.
  • [BGJT13] 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.
  • [Cop84] Don Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory 30 (1984), no. 4, 587-594. MR 755785 (85h:65041), https://doi.org/10.1109/TIT.1984.1056941
  • [DGV13] J. Detrey, P. Gaudry, and M. Videau, Relation collection for the function field sieve,
    In IEEE Symposium on Computer Arithmetic (ARITH 21), 2013.
  • [GGMZ13] 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.
  • [Har77] Robin Hartshorne, Algebraic Geometry, Springer-Verlag, New York, 1977. Graduate Texts in Mathematics, No. 52. MR 0463157 (57 #3116)
  • [HSST12] T. Hayashi, T. Shimoyama, N. Shinohara, and T. Takagi, Breaking pairing-based cryptosystems using $ \eta _t$ pairing over $ \textup {GF}(3^{97})$.
    In Advances in Cryptology - ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science, pages 43-60, 2012.
  • [HSW$^+$10] Takuya Hayashi, Naoyuki Shinohara, Lihua Wang, Shin'ichiro Matsuo, Masaaki Shirase, and Tsuyoshi Takagi, Solving a 676-bit discrete logarithm problem in $ \operatorname {GF}(3^{6n})$, Public key cryptography--PKC 2010, Lecture Notes in Comput. Sci., vol. 6056, Springer, Berlin, 2010, pp. 351-367. MR 2660752, https://doi.org/10.1007/978-3-642-13013-7_21
  • [IR90] 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 (92e:11001)
  • [JL02] 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 (2005j:11090), https://doi.org/10.1007/3-540-45455-1_34
  • [JL03] 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 (electronic). MR 1954978 (2003k:11192), https://doi.org/10.1090/S0025-5718-02-01482-5
  • [JL06] 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 (2009e:11229), https://doi.org/10.1007/11761679_16
  • [JL07] 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.
  • [Jou13a] 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
  • [Jou13b] 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/.
  • [Lor96] Dino Lorenzini, An Invitation to Arithmetic Geometry, Graduate Studies in Mathematics, vol. 9, American Mathematical Society, Providence, RI, 1996. MR 1376367 (97e:14035)
  • [Mat99] 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.
  • [Mon06] 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.
  • [Mur99] B.A. Murphy,
    Polynomial selection for the number field sieve integer factorisation algorithm,
    PhD thesis, Australian National University, 1999.
  • [Neu99] 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 (2000m:11104)
  • [PZ11] 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, https://doi.org/10.1016/j.jsc.2011.09.004
  • [Tho03] E. Thomé.
    Algorithmes de calcul des logarithmes discrets dans les corps finis,
    PhD thesis, École Polytechnique, Palaiseau, France, 2003.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 12Y05, 12F15

Retrieve articles in all journals with MSC (2010): 12Y05, 12F15


Additional Information

Razvan Barbulescu
Affiliation: Université de Lorraine, CNRS, INRIA, France
Email: razvan.barbulescu@inria.fr

DOI: https://doi.org/10.1090/S0025-5718-2015-02940-8
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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society