A polynomial factorization challenge

ABSTRACT

In the early 1970s, a major paradigm shift took place in algorithms research, away from experimental results to asymptotic analysis. Knuth popularized the "Big O" notation, and Hopcroft says in his 1986 ACM Turing Award (with Robert Tarjan) address: "During the 1960s, research on algorithms had been very unsatisfying. A researcher would publish an algorithm in a journal along with execution times for a small set of sample problems, and then several years later, a second researcher would give an improved algorithm along with execution times for the same set of sample problems. The new algorithm would invariably be faster, since in the intervening years, both computer performance and programming languages had improved. The fact that the algorithms were run on different computers and programmed in different languages made me uncomfortable with the comparison. It was difficult to factor out both the effects of increased computer performance and the programming skills of the implementors---to discover the effects due to the new algorithm as opposed to its implementation. Furthermore, it was possible that the second researcher had inadvertently tuned his or her algorithm to the sample problems ... I set out to demonstrate that a theory of algorithm design based on worst-case asymptotic performance could be a valuable aid to the practitioner."

REFERENCES

• 1: J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., <i>Factorizations of</i> <i>bⁿ</i> &plusmn; 1, <i>b</i> = 2,3,5,6,7,10,11,12 <i>Up to High Powers</i>, vol. 22 of <i>Contemporary Mathematics.</i> American Mathematical Society, 1988, 2nd edition.
• 2: Joachim von zur Gathen , Victor Shoup, Computing Frobenius maps and factoring polynomials, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.97-105, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129722]
• 3: E. Kaltofen, Polynomial factorization 1982--1986. In <i>Computers in Mathematics</i>, ed. D. V. Chudnovsky and R. D. Jenks, Marcel Dekker, New York, 1990, 285--309.
• 4: Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
• 5: A. K. Lenstra , H. W. Lenstra, Jr. , M. S. Manasse , J. M. Pollard, The number field sieve, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.564-572, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100295]

INDEX TERMS

Primary 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, Design, Theory