Smoothness testing of polynomials over finite fields

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

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, 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, ().
[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.

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, 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, ().
[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.

[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]	Grégory Berhuy, Jean Fasel, Odile Garotta. Rank weights for arbitrary finite field extensions. Advances in Mathematics of Communications, 2021, 15 (4) : 575-587. doi: 10.3934/amc.2020083
[4]	Eric Dubach, Robert Luce, Jean-Marie Thomas. Pseudo-Conform Polynomial Lagrange Finite Elements on Quadrilaterals and Hexahedra. Communications on Pure and Applied Analysis, 2009, 8 (1) : 237-254. doi: 10.3934/cpaa.2009.8.237
[5]	László Mérai, Igor E. Shparlinski. Unlikely intersections over finite fields: Polynomial orbits in small subgroups. Discrete and Continuous Dynamical Systems, 2020, 40 (2) : 1065-1073. doi: 10.3934/dcds.2020070
[6]	Artur Avila, Sébastien Gouëzel, Masato Tsujii. Smoothness of solenoidal attractors. Discrete and Continuous Dynamical Systems, 2006, 15 (1) : 21-35. doi: 10.3934/dcds.2006.15.21
[7]	C. Xiong, J.P. Miller, F. Gao, Y. Yan, J.C. Morris. Testing increasing hazard rate for the progression time of dementia. Discrete and Continuous Dynamical Systems - B, 2004, 4 (3) : 813-821. doi: 10.3934/dcdsb.2004.4.813
[8]	Laura Aquilanti, Simone Cacace, Fabio Camilli, Raul De Maio. A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions. Journal of Dynamics and Games, 2021, 8 (1) : 35-59. doi: 10.3934/jdg.2020033
[9]	Angela Aguglia, Antonio Cossidente, Giuseppe Marino, Francesco Pavese, Alessandro Siciliano. Orbit codes from forms on vector spaces over a finite field. Advances in Mathematics of Communications, 2022, 16 (1) : 135-155. doi: 10.3934/amc.2020105
[10]	Jaime Gutierrez. Reconstructing points of superelliptic curves over a prime finite field. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022022
[11]	A. Naga, Z. Zhang. The polynomial-preserving recovery for higher order finite element methods in 2D and 3D. Discrete and Continuous Dynamical Systems - B, 2005, 5 (3) : 769-798. doi: 10.3934/dcdsb.2005.5.769
[12]	David Salas, Lionel Thibault, Emilio Vilches. On smoothness of solutions to projected differential equations. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2255-2283. doi: 10.3934/dcds.2019095
[13]	Tomáš Smejkal, Jiří Mikyška, Jaromír Kukal. Comparison of modern heuristics on solving the phase stability testing problem. Discrete and Continuous Dynamical Systems - S, 2021, 14 (3) : 1161-1180. doi: 10.3934/dcdss.2020227
[14]	Philippe Destuynder, Caroline Fabre. Few remarks on the use of Love waves in non destructive testing. Discrete and Continuous Dynamical Systems - S, 2016, 9 (2) : 427-444. doi: 10.3934/dcdss.2016005
[15]	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
[16]	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
[17]	Farzane Amirzade, Mohammad-Reza Sadeghi, Daniel Panario. QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field. Advances in Mathematics of Communications, 2020, 14 (3) : 397-411. doi: 10.3934/amc.2020062
[18]	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
[19]	Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089
[20]	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 and Imaging, 2013, 7 (3) : 947-959. doi: 10.3934/ipi.2013.7.947

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Jean-François Biasse Michael J. Jacobson, Jr.
on Google Scholar
Jean-François Biasse Michael J. Jacobson, Jr.

[Back to Top]