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, (2010), 50.  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.  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.  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, (2013), 201.  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.  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.   Google Scholar

[9]

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

[10]

R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications,, Cambridge Univ. Press, (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., (1985), 224.  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.   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.  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.  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, (2010), 50.  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.  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.  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, (2013), 201.  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.  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.   Google Scholar

[9]

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

[10]

R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications,, Cambridge Univ. Press, (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., (1985), 224.  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.   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.  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.  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, 2019, 0 (0) : 0-0. 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 - A, 2020, 40 (2) : 1065-1073. doi: 10.3934/dcds.2020070
[6]

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

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

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

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

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

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

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

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

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

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
[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, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020062
[17]

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

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

Yaozhong Hu, David Nualart, Xiaobin Sun, Yingchao Xie. Smoothness of density for stochastic differential equations with Markovian switching. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3615-3631. doi: 10.3934/dcdsb.2018307
[20]

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

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (28)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences