Article Contents
Article Contents

# Smoothness testing of polynomials over finite fields

• We present an analysis of Bernstein's batch integer smoothness test when applied to the case of polynomials over a finite field $\mathbb{F}_q.$ We compare the performance of our algorithm with the standard method based on distinct degree factorization from both an analytical and a practical point of view. Our results show that although the batch test is asymptotically better as a function of the degree of the polynomials to test for smoothness, it is unlikely to offer significant practical improvements for cases of practical interest.
Mathematics Subject Classification: Primary: 11R11, 11R29, 11Y40; Secondary: 11Y16.

 Citation:

•  [1] gf2x, a C/C++ software package containing routines for fast arithmetic in $GF(2)[x]$ (multiplication, squaring, GCD) and searching for irreducible/primitive trinomials, available online at http://gf2x.gforge.inria.fr/ [2] D. Bernstein, How to find smooth parts of integers, submitted. [3] J.-F. Biasse and M. Jacobson, Practical improvements to class group and regulator computation of real quadratic fields, in Algorithmic Number Theory (eds. G. Hanrot, F. Morain and E. Thomé), Springer-Verlag, 2010, 50-65.doi: 10.1007/978-3-642-14518-6_8. [4] G. Bisson and A. Sutherland, Computing the endomorphism ring of an ordinary elliptic curve over a finite field, J. Number Theory, 113 (2011), 815-831.doi: 10.1016/j.jnt.2009.11.003. [5] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inf. Theory, 30 (1984), 587-594.doi: 10.1109/TIT.1984.1056941. [6] J. Detrey, P. Gaudry and M. Videau, Relation collection for the function field sieve, in 21st IEEE Int. Symp. Computer Arith. (eds. A. Nannarelli, P.-M. Seidel and P. Tang), IEEE, 2013, 201-210.doi: 10.1109/ARITH.2013.28. [7] A. Enge and P. Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith., 102 (2002), 83-103.doi: 10.4064/aa102-1-6. [8] M. Jacobson, A. Menezes and A. Stein, Solving elliptic curve discrete logarithm problems using Weil descent, J. Ramanujan Math. Soc., 16 (2001), 231-260. [9] H. Lenstra, Factoring integers with elliptic curves, Ann. Math., 126 (1987), 649-673.doi: 10.2307/1971363. [10] R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge Univ. Press, New York, 1986. [11] A. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, in Proc. EUROCRYPT 84 Workshop Adv. Cryptology: Theory Appl. Crypt. Techn., Springer-Verlag, New York, 1985, 224-314.doi: 10.1007/3-540-39757-4_20. [12] A. Schnhage and V. Strassen, Schnelle Multiplikation grosser Zahlen (in German), Computing, 7 (1971), 281-292. [13] V. Shoup, NTL: A library for doing number theory, Software, http://www.shoup.net/ntl [14] M. Velichka, M. Jacobson and A. Stein, Computing discrete logarithms in the jacobian of high-genus hyperelliptic curves over even characteristic finite fields, Math. Comp., 83 (2014), 935-963.doi: 10.1090/S0025-5718-2013-02748-2. [15] J. von zur Gathen and V. Shoup, Computing Frobenius maps and factoring polynomials, Comp. Complexity, 2 (1992), 187-224.doi: 10.1007/BF01272074.