Smoothness testing of polynomials over finite fields

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

November 2014, 8(4): 459-477. doi: 10.3934/amc.2014.8.459

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, Canada

Received January 2014 Revised September 2014 Published November 2014

Abstract
Related Papers

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: polynomial, finite field., Smoothness testing.

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

Citation: Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459

References:

[1]	gf2x, a C/C++ software package containing routines for fast arithmetic in $GF(2)[x]$, (multiplication, ().
[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*, (2010), 50. 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. 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. 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*, (2013), 201. 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. 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.
[9]	H. Lenstra, Factoring integers with elliptic curves,, Ann. Math., 126 (1987), 649. doi: 10.2307/1971363.
[10]	R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications,, Cambridge Univ. Press, (1986).
[11]	A. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance,, in Proc. EUROCRYPT 84 Workshop Adv. Cryptology: Theory Appl. Crypt. Techn., (1985), 224. doi: 10.1007/3-540-39757-4_20.
[12]	A. Schnhage and V. Strassen, Schnelle Multiplikation grosser Zahlen (in German),, Computing, 7 (1971), 281.
[13]	V. Shoup, NTL: A library for doing number theory,, Software, ().
[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. 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. doi: 10.1007/BF01272074.

show all references

References:

[1]	gf2x, a C/C++ software package containing routines for fast arithmetic in $GF(2)[x]$, (multiplication, ().
[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*, (2010), 50. 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. 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. 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*, (2013), 201. 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. 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.
[9]	H. Lenstra, Factoring integers with elliptic curves,, Ann. Math., 126 (1987), 649. doi: 10.2307/1971363.
[10]	R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications,, Cambridge Univ. Press, (1986).
[11]	A. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance,, in Proc. EUROCRYPT 84 Workshop Adv. Cryptology: Theory Appl. Crypt. Techn., (1985), 224. doi: 10.1007/3-540-39757-4_20.
[12]	A. Schnhage and V. Strassen, Schnelle Multiplikation grosser Zahlen (in German),, Computing, 7 (1971), 281.
[13]	V. Shoup, NTL: A library for doing number theory,, Software, ().
[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. 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. doi: 10.1007/BF01272074.

[1]	John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7.
[2]	Palash Sarkar, Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 2019, 13 (3) : 435-455. doi: 10.3934/amc.2019028
[3]	Eric Dubach, Robert Luce, Jean-Marie Thomas. Pseudo-Conform Polynomial Lagrange Finite Elements on Quadrilaterals and Hexahedra. Communications on Pure & Applied Analysis, 2009, 8 (1) : 237-254. doi: 10.3934/cpaa.2009.8.237
[4]	C. Xiong, J.P. Miller, F. Gao, Y. Yan, J.C. Morris. Testing increasing hazard rate for the progression time of dementia. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 813-821. doi: 10.3934/dcdsb.2004.4.813
[5]	Artur Avila, Sébastien Gouëzel, Masato Tsujii. Smoothness of solenoidal attractors. Discrete & Continuous Dynamical Systems - A, 2006, 15 (1) : 21-35. doi: 10.3934/dcds.2006.15.21
[6]	A. Naga, Z. Zhang. The polynomial-preserving recovery for higher order finite element methods in 2D and 3D. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 769-798. doi: 10.3934/dcdsb.2005.5.769
[7]	David Salas, Lionel Thibault, Emilio Vilches. On smoothness of solutions to projected differential equations. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2255-2283. doi: 10.3934/dcds.2019095
[8]	Philippe Destuynder, Caroline Fabre. Few remarks on the use of Love waves in non destructive testing. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 427-444. doi: 10.3934/dcdss.2016005
[9]	Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265
[10]	Keisuke Hakuta, Hisayoshi Sato, Tsuyoshi Takagi. On tameness of Matsumoto-Imai central maps in three variables over the finite field $\mathbb F_2$. Advances in Mathematics of Communications, 2016, 10 (2) : 221-228. doi: 10.3934/amc.2016002
[11]	Tetsuya Ishiwata, Kota Kumazaki. Structure preserving finite difference scheme for the Landau-Lifshitz equation with applied magnetic field. Conference Publications, 2015, 2015 (special) : 644-651. doi: 10.3934/proc.2015.0644
[12]	Yi Shi, Kai Bao, Xiao-Ping Wang. 3D adaptive finite element method for a phase field model for the moving contact line problems. Inverse Problems & Imaging, 2013, 7 (3) : 947-959. doi: 10.3934/ipi.2013.7.947
[13]	Eric A. Carlen, Süleyman Ulusoy. Localization, smoothness, and convergence to equilibrium for a thin film equation. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4537-4553. doi: 10.3934/dcds.2014.34.4537
[14]	Lev Buhovski, Roman Muraviev. Growth gap versus smoothness for diffeomorphisms of the interval. Journal of Modern Dynamics, 2008, 2 (4) : 629-643. doi: 10.3934/jmd.2008.2.629
[15]	Yaozhong Hu, David Nualart, Xiaobin Sun, Yingchao Xie. Smoothness of density for stochastic differential equations with Markovian switching. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-17. doi: 10.3934/dcdsb.2018307
[16]	Helmut Hofer, Kris Wysocki, Eduard Zehnder. Sc-smoothness, retractions and new models for smooth spaces. Discrete & Continuous Dynamical Systems - A, 2010, 28 (2) : 665-788. doi: 10.3934/dcds.2010.28.665
[17]	Marco Cappiello, Fabio Nicola. Sharp decay estimates and smoothness for solutions to nonlocal semilinear equations. Discrete & Continuous Dynamical Systems - A, 2016, 36 (4) : 1869-1880. doi: 10.3934/dcds.2016.36.1869
[18]	Yemin Chen. Smoothness of classical solutions to the Vlasov-Poisson-Landau system. Kinetic & Related Models, 2008, 1 (3) : 369-386. doi: 10.3934/krm.2008.1.369
[19]	Yemin Chen. Smoothness of classical solutions to the Vlasov-Maxwell-Landau system near Maxwellians. Discrete & Continuous Dynamical Systems - A, 2008, 20 (4) : 889-910. doi: 10.3934/dcds.2008.20.889
[20]	Rafaela Guberović. Smoothness of Koch-Tataru solutions to the Navier-Stokes equations revisited. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 231-236. doi: 10.3934/dcds.2010.27.231

2017 Impact Factor: 0.564

American Institute of Mathematical Sciences