\`x^2+y_1+z_12^34\`
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.

    Citation:

    \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/

    [2]

    D. BernsteinHow 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.

  • 加载中
SHARE

Article Metrics

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

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return