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]

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, 2020  doi: 10.3934/jdg.2020033
[2]

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

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

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[5]

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

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010
[7]

Jan Bouwe van den Berg, Elena Queirolo. A general framework for validated continuation of periodic orbits in systems of polynomial ODEs. Journal of Computational Dynamics, 2021, 8 (1) : 59-97. doi: 10.3934/jcd.2021004
[8]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267
[9]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[10]

Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111
[11]

Josselin Garnier, Knut Sølna. Enhanced Backscattering of a partially coherent field from an anisotropic random lossy medium. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1171-1195. doi: 10.3934/dcdsb.2020158
[12]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178
[13]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095
[14]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[15]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[16]

Bin Wang, Lin Mu. Viscosity robust weak Galerkin finite element methods for Stokes problems. Electronic Research Archive, 2021, 29 (1) : 1881-1895. doi: 10.3934/era.2020096
[17]

Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097
[18]

Jiwei Jia, Young-Ju Lee, Yue Feng, Zichan Wang, Zhongshu Zhao. Hybridized weak Galerkin finite element methods for Brinkman equations. Electronic Research Archive, , () : -. doi: 10.3934/era.2020126
[19]

Duy Phan, Lassi Paunonen. Finite-dimensional controllers for robust regulation of boundary control systems. Mathematical Control & Related Fields, 2021, 11 (1) : 95-117. doi: 10.3934/mcrf.2020029
[20]

Anton A. Kutsenko. Isomorphism between one-dimensional and multidimensional finite difference operators. Communications on Pure & Applied Analysis, 2021, 20 (1) : 359-368. doi: 10.3934/cpaa.2020270

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences