|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 ABSTRACT
The problem of factoring a polynomial in a single or several variables over a finite field, the rational numbers or the complex numbers is one of the success stories in the discipline of symbolic computation. In the early 1960s implementors investigated the constructive methods known from classical algebra books, but--with the exception of Gauss's distinct degree factorization algorithm--found the algorithms quite inefficient in practice [16]. The contributions in algorithmic techniques that have been made over the next 40 years are truly a hallmark of symbolic computation research. The early pioneers, Berlekamp, Musser, Wang, Weinberger, Zassenhaus and others applied new ideas like randomization, that even before the now famous algorithms for primality testing by Rabin and Strassen, and like generic programming with coefficient domains as abstract data classes, and they introduced the powerful Hensel lifting lemma to computer algebra. We note that while de-randomization for integer primality testing has been accomplished recently [1], the same remains open for the problem of computing a root of a polynomial modulo a large prime [12, Research Problem 14.48]. Polynomial-time complexity for rational coefficients was established in the early 1980s by the now-famous lattice basis reduction algorithm of A. Lenstra, H. W. Lenstra, Jr., and L. Lovász. The case of many variables first became an application of the DeMillo and Lipton/Schwartz/Zippel lemma [30] and then triggered a fundamental generalization from the standard sparse (distributed) representation of polynomials to the one by straight line and black box programs [11, 17, 19]. Effective versions of the Hilbert irreducibility theorem are needed for the probabilistic analysis, which serendipitously later have also played a role in the PCP characterization of <i>NP</i> [2]. Unlike many other problems in commutative algebra and algebraic geometry, such as algebraic system solving, the polynomial factoring problem is of probabilistic polynomial-time complexity in the number of variables. Complex coefficients in multivariate factors can be represented either by exact algebraic numbers or by imprecise floating point numbers. The latter formulation is a cornerstone in the new computer algebra subject of SNAP (Symbolic-Numeric Algorthms for Polynomials) (see, e.g., [4]). The approaches for both exact and imprecise coefficients are manifold, including Ruppert's partial differential equations [26, 27, 6, 10] and Gao's and Lauder's far-reaching generalization of Eisenstein's criterion in the multivariate case to Newton polytope decomposition [8, 9]. The currently best algorithms were all discovered recently within the past ten years. The baby steps/giant steps technique and fast distinct and equal degree factorization implementations have, at last, yielded in the mid 1990s theoretical and practical improvements over the original univariate Berlekamp algorithm for coefficients in finite fields [13, 29, 18, 3]. The average time analysis for selected algorithms is also completed [5]. For bivariate polynomials over finite fields, surprisingly Gröbner basis techniques are useful in practice [23]. New polynomial-time complexity results are the computation of low degree factors of very high degree sparse (lacunary) polynomials by H. W. Lenstra, Jr. [20, 21], and the deterministic distinct degree factorization for multivariate polynomials over large finite fields [7]. However, many problems with high degree polynomials over large finite fields in sparse or straight line program representations, such as computing a root modulo a large prime, are not known to be in random polynomial time or NP-hard (cf. [24, 25, 15]). Finally, in 2000 Mark van Hoeij [14] reintroduced lattice basis reduction, now in the Berlekamp-Zassenhaus algorithm, to conquer the hard-to-factor Swinnerton-Dyer polynomials in practice. Sasaki in 1993 had already hinted of the used approach [28]. In my talk I will discuss a selection of the highlights, state remaining open problems, and give some applications including an unusual one due to Moni Naor [22]. REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
INDEX TERMS
Primary Classification:
Keywords:
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Terms of Usage Privacy Policy Code of Ethics Contact Us Useful downloads:  Adobe Acrobat
 QuickTime
 Windows Media Player
 Real Player
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Pdf
F.2