More Web Proxy on the site http://driver.im/

Article

Complexity issues in bivariate polynomial factorization

Authors:

B. WiebeltAuthors Info & Claims

ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation

Pages 42 - 49

https://doi.org/10.1145/1005285.1005294

Published: 04 July 2004 Publication History

Abstract

Many polynomial factorization algorithms rely on Hensel lifting and factor recombination. For bivariate polynomials we show that lifting the factors up to a precision linear in the total degree of the polynomial to be factored is sufficient to deduce the recombination by linear algebra, using trace recombination. Then, the total cost of the lifting and the recombination stage is subquadratic in the size of the dense representation of the input polynomial. Lifting is often the practical bottleneck of this method: we propose an algorithm based on a faster multi-moduli computation for univariate polynomials and show that it saves a constant factor compared to the classical multifactor lifting algorithm.

References

[1]

K. Belabas, M. van Hoeij, J. Klüuners, and A. Steel. Factoring polynomials over global fields. 2003.

[2]

L. Bernardin. On bivariate Hensel lifting and its parallelization. In ISSAC'98, pages 96--100. ACM Press, 1998.

Digital Library

[3]

D. J. Bernstein. Fast multiplication and its applications. Manuscript, 2003.

[4]

A. Bostan, G. Lecerf, and É. Schost. Tellegen's principle into practice. In ISSAC'03, pages 37--44. ACM Press, 2003.

Digital Library

[5]

A. Bostan, B. Salvy, and É. Schost. Fast algorithms for zero-dimensional polynomial systems using duality. AAECC, 14(4):239--272, 2003.

[6]

P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory. Springer, Berlin, 1997.

Digital Library

[7]

S. Gao. Factoring multivariate polynomials via partial differential equations. Math. Comp., 72:801--822, 2003.

Digital Library

[8]

J. von zur Gathen. Hensel and Newton methods in valuation rings. Math. Comp., 42(166):637--661, 1984.

[9]

J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 1st edition, 1999.

Digital Library

[10]

J. von zur Gathen and E. Kaltofen. Factoring sparse multivariate polynomials. J. Comput. System Sci., 31:265--287, 1985.

Digital Library

[11]

J. von zur Gathen and E. Kaltofen. Factorization of multivariate polynomials over finite fields. Math. Comp., 45:251--261, 1985.

[12]

G. Hanrot, M. Quercia, and P. Zimmermann. The Middle Product Algorithm, I. Appl. Algebra Engrg. Comm. Comput., 14(6):415--438, 2004.

Digital Library

[13]

M. van Hoeij. Factoring polynomials and the knapsack problem. J. Number Theory, 95(2):167--189, 2002.

[14]

E. Kaltofen. Polynomial factorization. In B. Buchberger, G. Collins, and R. Loos, editors, Computer algebra, pages 95--113. Springer, 1982.

[15]

E. Kaltofen. Sparse Hensel lifting. In EUROCAL'85, Vol. 2 (Linz, 1985), volume 204 of LNCS, pages 4--17. Springer, Berlin, 1985.

Digital Library

[16]

E. Kaltofen. Factorization of polynomials given by straight-line programs. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 375--412. JAI, 1989.

[17]

E. Kaltofen. Polynomial factorization: a success story. In ISSAC'03, pages 3--4. ACM Press, 2003.

Digital Library

[18]

E. Kaltofen and B. Trager. Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separations of enumerators and denominators. J. Symb. Comput., 9(3):301--320, 1990.

Digital Library

[19]

G. Lecerf. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. J. Complexity, 19(4):564--596, 2003.

Digital Library

[20]

A. K. Lenstra. Factoring multivariate polynomials over finite fields. J. Comput. System Sci., 2:235--248, 1985.

[21]

D. R. Musser. Multivariate polynomial factorization. J. Assoc. Comput. Mach., 22:291--308, 1975.

Digital Library

[22]

K. Nagasaka and T. Sasaki. Approximate multivariate polynomial factorization and its time complexity, 1998. preprint.

[23]

M. Noro and K. Yokoyama. Yet another practical implementation of polynomial factorization over finite fields. In ISSAC'02, pages 200--206. ACM Press, 2002.

Digital Library

[24]

T. Sasaki, T. Saito, and T. Hilano. Analysis of approximate factorization algorithm. I. Japan J. Indust. Appl. Math., 9(3):351--368, 1992.

[25]

T. Sasaki and M. Sasaki. A unified method for multivariate polynomial factorizations. Japan J. Indust. Appl. Math., 10(1):21--39, 1993.

[26]

T. Sasaki, M. Suzuki, M. Kolář, and M. Sasaki. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indust. Appl. Math., 8(3):357--375, 1991.

[27]

V. Shoup. NTL: A library for doing number theory. http://www.shoup.net.

[28]

A. Storjohann. Algorithms for matrix canonical forms. PhD thesis, ETH, Zürich, 2000.

[29]

P. S. Wang. An improved multivariate polynomial factoring algorithm. Math. Comp., 32(144):1215--1231, 1978.

[30]

P. S. Wang and L. P. Rothschild. Factoring multivariate polynomials over the integers. Math. Comp., 29:935--950, 1975.

[31]

D. Y. Y. Yun. Uniform bounds for a class of algebraic mappings. SIAM J. on Computing, 8:348--356, 1979.

Digital Library

[32]

H. Zassenhaus. On Hensel factorization I. J. Number Theory, 1(1):291--311, 1969.

[33]

H. Zassenhaus. A remark on the Hensel factorization method. Math. Comp., 32(141):287--292, 1978.

[34]

R. Zippel. Effective Polynomial Computation. Kluwer Academic Publishers, 1993.

Cited By

van der Hoeven JLecerf G(2024)Plane curve germs and contact factorizationApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-024-00669-zOnline publication date: 30-Nov-2024
https://doi.org/10.1007/s00200-024-00669-z
Huang QGao X(2023)New Sparse Multivariate Polynomial Factorization Algorithms over IntegersProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597087(315-324)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597087
Coxon N(2020)Fast Hermite interpolation and evaluation over finite fields of characteristic twoJournal of Symbolic Computation10.1016/j.jsc.2019.07.01498:C(270-283)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1016/j.jsc.2019.07.014
Show More Cited By

Index Terms

Complexity issues in bivariate polynomial factorization
1. Mathematics of computing
  1. Mathematical software

Recommendations

New bivariate Hensel lifting algorithm for n factors

We present a new algorithm for performing linear Hensel lifting of bivariate polynomials over a finite field F_p with p elements. It lifts n monic, univariate polynomials to recover the factors of a polynomial A(x, y) ∈ F_p[x, y] which is monic in x, and ...
Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization

Consider a polynomial f with an arbitrary but fixed number of variables and with integral coefficients. We present an algorithm which reduces the problem of finding the irreducible factors of f in polynomial-time in the total degree of f and the ...
Improved dense multivariate polynomial factorization algorithms

We present new deterministic and probabilistic algorithms that reduce the factorization of dense polynomials from several variables to one variable. The deterministic algorithm runs in sub-quadratic time in the dense size of the input polynomial, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation

July 2004

334 pages

ISBN:158113827X

DOI:10.1145/1005285

General Chair:
Josef Schicho
RICAM, Austrian Academy of Sciences, Linz, Austria

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 July 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC04

Sponsor:

ISSAC04: International Symposium on Symbolic and Algebraic Computation

July 4 - 7, 2004

Santander, Spain

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
369
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

van der Hoeven JLecerf G(2024)Plane curve germs and contact factorizationApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-024-00669-zOnline publication date: 30-Nov-2024
https://doi.org/10.1007/s00200-024-00669-z
Huang QGao X(2023)New Sparse Multivariate Polynomial Factorization Algorithms over IntegersProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597087(315-324)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597087
Coxon N(2020)Fast Hermite interpolation and evaluation over finite fields of characteristic twoJournal of Symbolic Computation10.1016/j.jsc.2019.07.01498:C(270-283)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1016/j.jsc.2019.07.014
Monagan MDavenport JWang DKauers MBradford R(2019)Linear Hensel Lifting for Fp[x,y] and Z[x] with Cubic CostProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326242(299-306)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326242
Chèze GCombot T(2019)Symbolic Computations of First Integrals for Polynomial Vector FieldsFoundations of Computational Mathematics10.1007/s10208-019-09437-9Online publication date: 27-Sep-2019
https://doi.org/10.1007/s10208-019-09437-9
Allem LCapaverde Jvan Hoeij MSzutkoski JYap CEl Din M(2017)Functional Decomposition Using Principal SubfieldsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087608(421-428)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087608
Weimann M(2017)Bivariate Factorization Using a Critical FiberFoundations of Computational Mathematics10.1007/s10208-016-9318-817:5(1219-1263)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s10208-016-9318-8
Blankertz R(2014)A polynomial time algorithm for computing all minimal decompositions of a polynomialACM Communications in Computer Algebra10.1145/2644288.264429248:1/2(13-23)Online publication date: 10-Jul-2014
https://dl.acm.org/doi/10.1145/2644288.2644292
Wu WChen JFeng Y(2014)Sparse bivariate polynomial factorizationScience China Mathematics10.1007/s11425-014-4850-y57:10(2123-2142)Online publication date: 26-Jun-2014
https://doi.org/10.1007/s11425-014-4850-y
Salem FEl-Harake KGemayel K(2014)Factoring Sparse Bivariate Polynomials Using the Priority QueueComputer Algebra in Scientific Computing10.1007/978-3-319-10515-4_28(388-402)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10515-4_28
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents