Advanced Search
Article Contents
Article Contents

Smoothness testing of polynomials over finite fields

Abstract Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • [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/


    D. BernsteinHow to find smooth parts of integers, submitted.


    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.


    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.


    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.


    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.


    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.


    M. Jacobson, A. Menezes and A. Stein, Solving elliptic curve discrete logarithm problems using Weil descent, J. Ramanujan Math. Soc., 16 (2001), 231-260.


    H. Lenstra, Factoring integers with elliptic curves, Ann. Math., 126 (1987), 649-673.doi: 10.2307/1971363.


    R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge Univ. Press, New York, 1986.


    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.


    A. Schnhage and V. Strassen, Schnelle Multiplikation grosser Zahlen (in German), Computing, 7 (1971), 281-292.


    V. Shoup, NTL: A library for doing number theory, Software, http://www.shoup.net/ntl


    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.


    J. von zur Gathen and V. Shoup, Computing Frobenius maps and factoring polynomials, Comp. Complexity, 2 (1992), 187-224.doi: 10.1007/BF01272074.

  • 加载中

Article Metrics

HTML views() PDF downloads(105) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint