Smoothness testing of polynomials over finite fields

Jean-François Biasse; Michael J. Jacobson, Jr.

doi:10.3934/amc.2014.8.459

Article Contents

2014, Volume 8, Issue 4: 459-477. Doi: 10.3934/amc.2014.8.459

This issue Previous Article The geometry of some parameterizations and encodings Next Article Curves in characteristic $2$ with non-trivial $2$-torsion

Smoothness testing of polynomials over finite fields

Jean-François Biasse^1, and
Michael J. Jacobson, Jr.^2,

1.
Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
2.
Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4

Received: January 2014

Revised: September 2014

Published: November 2014

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 11R11, 11R29, 11Y40; Secondary: 11Y16.

Citation:

Related Papers

Cited by

References

[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.