American Institute of Mathematical Sciences

Advanced
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

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

[2]

D. Bernstein, How to find smooth parts of integers,, submitted., ().   Google Scholar

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

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

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

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

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

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

[9]

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

[10]

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

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

[12]

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

[13]

V. Shoup, NTL: A library for doing number theory,, Software, ().   Google Scholar

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

[15]

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

show all references

References:
[1]

gf2x, a C/C++ software package containing routines for fast arithmetic in $GF(2)[x]$, (multiplication, ().   Google Scholar

[2]

D. Bernstein, How to find smooth parts of integers,, submitted., ().   Google Scholar

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

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

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

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

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

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

[9]

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

[10]

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

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

[12]

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

[13]

V. Shoup, NTL: A library for doing number theory,, Software, ().   Google Scholar

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

[15]

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

[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 & 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 & 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 & 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 & Continuous Dynamical Systems - B, 2004, 4 (3) : 813-821. doi: 10.3934/dcdsb.2004.4.813
[8]

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, 2020  doi: 10.3934/amc.2020105
[9]

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 & Games, 2021, 8 (1) : 35-59. doi: 10.3934/jdg.2020033
[10]

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
[11]

David Salas, Lionel Thibault, Emilio Vilches. On smoothness of solutions to projected differential equations. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 2255-2283. doi: 10.3934/dcds.2019095
[12]

Tomáš Smejkal, Jiří Mikyška, Jaromír Kukal. Comparison of modern heuristics on solving the phase stability testing problem. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1161-1180. doi: 10.3934/dcdss.2020227
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, 2021, 29 (3) : 2517-2532. doi: 10.3934/era.2020127

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (75)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences