A generalized class of polynomials that are hard to factor

ABSTRACT

A class of univariate polynomials is defined which make the Berlekamp-Hensel factorization algorithm take an exponential amount of time. The class contains as subclasses the Swinnerton-Dyer polynomials discussed by Berlekamp and a subset of the cyclotomic polynomials. Aside from shedding light on the complexity of polynomial factorization this class is also useful in testing implementations of the Berlekamp-Hensel and related algorithms.

REFERENCES

• 1: E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comput. 24 (1970), pp. 713-735.
• 2: A. S. Besicovitch, On the linear independence of fractional powers of integers, J. London Math. Soc. 15 (1940), pp. 1-3.
• 3: B. F. Caviness, On Canonical Forms and Simplification, Carnegie-Mellon Univ., Ph.D. Thesis 1968.
• 4: George E. Collins, Factoring univariate integral polynomial in polynomial average time, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.317-329, June 01, 1979
• 5: L. Gaal, Classical Galois Theory with Examples, Chelsea Publ. Co., New York 1973.
• 6: G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Ed., Oxford Univ. Press, Oxford 1979.
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: S. Lang, Algebra, Addison-Wesley, Reading MA. 1971.
• 9: R. G. K. Loos, A constructive approach to algebraic numbers, Unpublished Article, May 1973.
• 10: David R. Musser, Multivariate Polynomial Factorization, Journal of the ACM (JACM), v.22 n.2, p.291-308, April 1975 [doi>10.1145/321879.321890]
• 11: M. O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), pp. 273-280.
• 12: I. Richards, An application of Galois theory to elementary arithmetic, Adv. in Math. 13 (1974), pp. 268-273.
• 13: W. Sierpinski, Elementary Theory of Numbers, Polish Sci. Publ., Warszawa 1964.
• 14: B. L. Van der Waerden, Modern Algebra, Vol. 1, Ungar Publ. Co., New York 1953.
• 15: Hans Zassenhaus, On the van der Waerden criterion for the group of an equation, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.95-107, June 01, 1979

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Theory