Article

Factoring polynomials via polytopes

Authors:

Fatima Abu Salem,

Shuhong Gao,

Alan G. B. LauderAuthors Info & Claims

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

Pages 4 - 11

https://doi.org/10.1145/1005285.1005289

Published: 04 July 2004 Publication History

Get Access

Abstract

We introduce a new approach to multivariate polynomial factorisation which incorporates ideas from polyhedral geometry, and generalises Hensel lifting. Our main contribution is to present an algorithm for factoring bivariate polynomials which is able to exploit to some extent the sparsity of polynomials. We give details of an implementation which we used to factor randomly chosen sparse and composite polynomials of high degree over the binary field.

References

[1]

F. Abu Salem, S. Gao, and A. G. B. Lauder "Factoring polynomials via polytopes: extended version", Report PRG-RR-04-07, Oxford University Computing Laboratory, 2004.

Google Scholar

[2]

S. Gao, "Absolute irreducibility of polynomials via Newton polytopes," J. of Algebra 237 (2001), 501--520.

Crossref

Google Scholar

[3]

S. Gao and A.G.B. Lauder, "Decomposition of polytopes and polynomials", Discrete and Computational Geometry 26 (2001), 89--104.

Digital Library

Google Scholar

[4]

S. Gao and A.G.B. Lauder, "Hensel lifting and bivariate polynomial factorisation over finite fields", Mathematics of Computation 71 (2002), 1663--1676.

Digital Library

Google Scholar

[5]

S. Gao and A.G.B. Lauder, Fast absolute irreducibility testing via Newton polytopes, preprint 2003.

Google Scholar

[6]

J. von zur Gathen and J. Gërhard, Modern Computer Algebra, Cambridge University Press, 1999.

Digital Library

Google Scholar

[7]

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

Digital Library

Google Scholar

[8]

R. L. Graham, "An efficient algorithm for determining the convex hull of a finite planar set", Inform. Process. Lett. 1 (1972), 132--3.

Crossref

Google Scholar

[9]

E. Kaltofen and B. Trager, "Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators", J. Symbolic Comput. 9 (1990), 301--320.

Digital Library

Google Scholar

[10]

D. Wan, "Factoring polynomials over large finite fields", Math. Comp. 54 (1990), No. 190, 755--770.

Crossref

Google Scholar

Cited By

View all

Emiris IKarasoulou ATzovas C(2017)Approximating Multidimensional Subset Sum and Minkowski Decomposition of PolygonsMathematics in Computer Science10.1007/s11786-017-0297-111:1(35-48)Online publication date: 24-Mar-2017
https://doi.org/10.1007/s11786-017-0297-1
Abu Salem FEl-Harake KGemayel KPernet C(2015)Cache oblivious sparse polynomial factoring using the funnel heapProceedings of the 2015 International Workshop on Parallel Symbolic Computation10.1145/2790282.2790283(7-15)Online publication date: 10-Jul-2015
https://dl.acm.org/doi/10.1145/2790282.2790283
Sanuki MInaba DSasaki T(2015)Computation of GCD of Sparse Multivariate Polynomials by Extended Hensel ConstructionProceedings of the 2015 17th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC.2015.15(34-41)Online publication date: 21-Sep-2015
https://dl.acm.org/doi/10.1109/SYNASC.2015.15
Show More Cited By

Index Terms

Factoring polynomials via polytopes
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

Polynomials arising in factoring generalized Vandermonde determinants: an algorithm for computing their coefficients

We consider generalized Vandermonde determinants of the form where the x"i are distinct points belonging to an interval [a, b] of the real line, the index s stands for the order, the sequence @m consists of ordered integers 0 @? @m"1 < @m"2 < ... < @m"...
Roots and coefficients of multivariate polynomials over finite fields

Kopparty and Wang studied in 3] the relation between the roots of a univariate polynomial over F q and the zero-nonzero pattern of its coefficients. We generalize their results to polynomials in more variables. We study the number of roots of ...
Symbolic-Numeric Computation of the Bernstein Coefficients of a Polynomial from Those of One of Its Partial Derivatives and of the Product of Two Polynomials
Computer Algebra in Scientific Computing
Abstract
The expansion of a given multivariate polynomial into Bernstein polynomials is considered. Matrix methods for the calculation of the Bernstein expansion of the product of two polynomials and of the Bernstein expansion of a polynomial from the ...

Comments

Information & Contributors

Information

Published In

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

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]

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

19
Total Citations
View Citations
355
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Emiris IKarasoulou ATzovas C(2017)Approximating Multidimensional Subset Sum and Minkowski Decomposition of PolygonsMathematics in Computer Science10.1007/s11786-017-0297-111:1(35-48)Online publication date: 24-Mar-2017
https://doi.org/10.1007/s11786-017-0297-1
Abu Salem FEl-Harake KGemayel KPernet C(2015)Cache oblivious sparse polynomial factoring using the funnel heapProceedings of the 2015 International Workshop on Parallel Symbolic Computation10.1145/2790282.2790283(7-15)Online publication date: 10-Jul-2015
https://dl.acm.org/doi/10.1145/2790282.2790283
Sanuki MInaba DSasaki T(2015)Computation of GCD of Sparse Multivariate Polynomials by Extended Hensel ConstructionProceedings of the 2015 17th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC.2015.15(34-41)Online publication date: 21-Sep-2015
https://dl.acm.org/doi/10.1109/SYNASC.2015.15
Grenet BNagasaka KWinkler FSzanto A(2014)Computing low-degree factors of lacunary polynomialsProceedings of the 39th International Symposium on Symbolic and Algebraic Computation10.1145/2608628.2608649(224-231)Online publication date: 23-Jul-2014
https://dl.acm.org/doi/10.1145/2608628.2608649
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
Mullen GPanario D(2013)CryptographyHandbook of Finite Fields10.1201/b15006-22(777-860)Online publication date: 17-Jun-2013
https://doi.org/10.1201/b15006-22
Wu WChen JFeng Y(2013)An efficient algorithm to factorize sparse bivariate polynomials over the rationalsACM Communications in Computer Algebra10.1145/2429135.242916546:3/4(125-126)Online publication date: 15-Jan-2013
https://dl.acm.org/doi/10.1145/2429135.2429165
Weimann M(2012)Algebraic Osculation and Application to Factorization of Sparse PolynomialsFoundations of Computational Mathematics10.5555/3115500.311591512:2(173-201)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.5555/3115500.3115915
Weimann M(2012)Algebraic Osculation and Application to Factorization of Sparse PolynomialsFoundations of Computational Mathematics10.1007/s10208-012-9114-z12:2(173-201)Online publication date: 22-Feb-2012
https://doi.org/10.1007/s10208-012-9114-z
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.

Cited By

Index Terms

Recommendations

Polynomials arising in factoring generalized Vandermonde determinants: an algorithm for computing their coefficients

Roots and coefficients of multivariate polynomials over finite fields

Symbolic-Numeric Computation of the Bernstein Coefficients of a Polynomial from Those of One of Its Partial Derivatives and of the Product of Two Polynomials

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Polynomials arising in factoring generalized Vandermonde determinants: an algorithm for computing their coefficients

Roots and coefficients of multivariate polynomials over finite fields

Symbolic-Numeric Computation of the Bernstein Coefficients of a Polynomial from Those of One of Its Partial Derivatives and of the Product of Two Polynomials

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations