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

research-article

Factoring bivariate lacunary polynomials without heights

Authors:

Arkadev Chattopadhyay,

Natacha Portier,

Yann StrozeckiAuthors Info & Claims

ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

Pages 141 - 148

https://doi.org/10.1145/2465506.2465932

Published: 26 June 2013 Publication History

Abstract

We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap theorem which allows to test whether P(X)=∑^k_j=1 α_jX^αj(1+X)^βjis identically zero in polynomial time. The algorithm we obtain is more elementary than the one by Kaltofen and Koiran (ISSAC'05) since it relies on the valuation of polynomials of the previous form instead of the height of the coefficients. As a result, it can be used to find some linear factors of bivariate lacunary polynomials over a field of large finite characteristic in probabilistic polynomial time.

References

[1]

J. Bi, Q. Cheng, and J. M. Rojas. Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields. In Proc. ISSAC, 2013. arXiv:1204.1113.

Digital Library

[2]

A. Bostan and P. Dumas. Wronskians and linear independence. Am. Math. Mon., 117(8):722--727, 2010.

[3]

A. Chattopadhyay, B. Grenet, P. Koiran, N. Portier, and Y. Strozecki. Factoring bivariate lacunary polynomials without heights. Xiv:1206.4224, 2012.

Digital Library

[4]

F. Cucker, P. Koiran, and S. Smale. A polynomial time algorithm for Diophantine equations in one variable. J. Symb. Comput., 27(1):21--30, 1999.

Digital Library

[5]

M. Filaseta, A. Granville, and A. Schinzel. Irreducibility and Greatest Common Divisor Algorithms for Sparse Polynomials. In Number Theory and Polynomials, volume 352 of P. Lond. Math. Soc., pages 155--176. Camb. U. Press, 2008.

[6]

S. Gao. Factoring multivariate polynomials via partial differential equations. Math. Comput., 72(242):801--822, 2003.

Digital Library

[7]

M. Giesbrecht and D. S. Roche. On lacunary polynomial perfect powers. In Proc. ISSAC'08, pages 103--110. ACM, 2008.

Digital Library

[8]

M. Giesbrecht and D. S. Roche. Detecting lacunary perfect powers and computing their roots. J. Symb. Comput., 46(11):1242--1259, 2011.

Digital Library

[9]

G. Hajós. {solution to problem 41} (in hungarian). Mat. Lapok, 4:40--41, 1953.

[10]

E. Kaltofen. Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization. SIAM J. Comput., 14(2):469--489, 1985.

Digital Library

[11]

E. Kaltofen and P. Koiran. On the complexity of factoring bivariate supersparse (lacunary) polynomials. In Proc. ISSAC'05, pages 208--215. ACM, 2005.

Digital Library

[12]

E. Kaltofen and P. Koiran. Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields. In Proc. ISSAC'06, pages 162--168. ACM, 2006.

Digital Library

[13]

E. L. Kaltofen and G. Lecerf. Factorization of Multivariate Polynomials. In Handbook of Finite Fields, Disc. Math. Appl. CRC Press, 2013. To appear.

[14]

E. L. Kaltofen and M. Nehring. Supersparse black box rational function interpolation. In Proc. ISSAC'11, pages 177--186. ACM, 2011.

Digital Library

[15]

I. Kaplansky. An introduction to differential algebra. Actualités scientifiques et industrielles. Hermann, 1976.

[16]

M. Karpinski and I. Shparlinski. On the computational hardness of testing square-freeness of sparse polynomials. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 1719 of LNCS, pages 731--731. Springer, 1999.

Digital Library

[17]

N. Kayal and C. Saha. On the Sum of Square Roots of Polynomials and Related Problems. In Proc. CCC'11, pages 292--299. IEEE, 2011.

Digital Library

[18]

A. Kipnis and A. Shamir. Cryptanalysis of the HFE public key cryptosystem by relinearization. In Proc. CRYPTO, pages 19--30. Springer, 1999.

Digital Library

[19]

P. Koiran, N. Portier, and S. Tavenas. A Wronskian approach to the real τ-conjecture.hrefhttp://arxiv.org/abs/1205.1015arXiv:1205.1015, 2012. Accepted for oral presentation at MEGA 2013.

[20]

G. Lecerf. Improved dense multivariate polynomial factorization algorithms. J. Symb. Comput., 42(4):477--494, 2007.

Digital Library

[21]

A. K. Lenstra. Factoring Multivariate Polynomials over Algebraic Number Fields. SIAM J. Comput., 16(3):591--598, 1987.

Digital Library

[22]

H. Lenstra Jr. Finding small degree factors of lacunary polynomials. In Number theory in progress, pages 267--276. De Gruyter, 1999.

[23]

É. Lucas. Théorie des fonctions numériques simplement périodiques. Amer. J. Math., 1(2--4):184--240,289--321, 1878.

[24]

H. Montgomery and A. Schinzel. Some arithmetic properties of polynomials in several variables. In Transcendence Theory: Advances and Applications, chapter 13, pages 195--203. Academic Press, 1977.

[25]

M. Petkov\v sek, H. S. Wilf, and D. Zeilberger. A=B. AK Peters, 1996.

[26]

D. Plaisted. Sparse complex polynomials and polynomial reducibility. J. Comput. Syst. Sci., 14(2):210--221, 1977.

[27]

J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Camb. U. Press, 2nd edition, 2003.

Digital Library

[28]

J. von zur Gathen, M. Karpinski, and I. Shparlinski. Counting curves and their projections. Comput. Complex., 6(1):64--99, 1996.

Digital Library

Cited By

Roche DKauers MOvchinnikov ASchost É(2018)What Can (and Can't) we Do with Sparse Polynomials?Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209027(25-30)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209027
Grenet B(2016)LacunaryxACM Communications in Computer Algebra10.1145/2893803.289380749:4(121-124)Online publication date: 17-Feb-2016
https://dl.acm.org/doi/10.1145/2893803.2893807
Grenet B(2016)Bounded-degree factors of lacunary multivariate polynomialsJournal of Symbolic Computation10.1016/j.jsc.2015.11.01375:C(171-192)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jsc.2015.11.013
Show More Cited By

Index Terms

Factoring bivariate lacunary polynomials without heights
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms

Recommendations

Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

We present a new algorithm for the computation of the irreducible factors of degree at most d, with multiplicity, of multivariate lacunary polynomials over fields of characteristic zero. The algorithm reduces this computation to the computation of ...
Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

We present algorithms that compute all irreducible factors of degree ≤ d of supersparse (lacunary) multivariate polynomials in n variables over an algebraic number field in deterministic polynomial-time in (l+d)ⁿ, where l is the size of the input ...
On the complexity of factoring bivariate supersparse (Lacunary) polynomials
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computation

We present algorithms that compute the linear and quadratic factors of supersparse (lacunary) bivariate polynomials over the rational numbers in polynomial-time in the input size. In supersparse polynomials, the term degrees can have hundreds of digits ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

June 2013

400 pages

ISBN:9781450320597

DOI:10.1145/2465506

General Chairs:
Michael Monagan
Simon Fraser University, Burnaby, Canada
,
Gene Cooperman
Northeastern University, Boston, USA
,
Program Chair:
Mark Giesbrecht
University of Waterloo, Waterloo, Canada

Copyright © 2013 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

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC'13

Sponsor:

SIGSAM

ISSAC'13: International Symposium on Symbolic and Algebraic Computation

June 26 - 29, 2013

Maine, Boston, USA

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
78
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Roche DKauers MOvchinnikov ASchost É(2018)What Can (and Can't) we Do with Sparse Polynomials?Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209027(25-30)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209027
Grenet B(2016)LacunaryxACM Communications in Computer Algebra10.1145/2893803.289380749:4(121-124)Online publication date: 17-Feb-2016
https://dl.acm.org/doi/10.1145/2893803.2893807
Grenet B(2016)Bounded-degree factors of lacunary multivariate polynomialsJournal of Symbolic Computation10.1016/j.jsc.2015.11.01375:C(171-192)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jsc.2015.11.013
Forbes M(2015)Deterministic Divisibility Testing via Shifted Partial DerivativesProceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2015.35(451-465)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1109/FOCS.2015.35
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

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