Smoothness testing of polynomials over finite fields
Jean‐François Biasse, Michael J. Jacobson · Advances in Mathematics of Communications · 2014
We present an analysis of Bernstein's batch integer smoothness testwhen applied to the case of polynomials over a finite field $\mathbb{F}_q.$ Wecompare the performance of our algorithm with the standard methodbased on distinct degree factorization from both an analytical and apractical point of view. Our results show that although the batchtest is asymptotically better as a function of the degree of thepolynomials to test for smoothness, it is unlikely to offersignificant practical improvements for cases of practical interest.