Detecting lacunary perfect powers and computing their roots

DOI10.1016/J.JSC.2011.08.006MaRDI QIDQ650838zbMATH OpenOpenAlexFDO

Authors Daniel S. Roche, Mark Giesbrecht

Publication date 7 December 2011

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2011.08.006

zbMATH Keywords

sparse polynomiallacunary representationperfect power

Mathematics Subject Classification ID

Polynomials in number theory (11C08) Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Polynomials, factorization in commutative rings (13P05)

Recommendations

• On lacunary polynomial perfect powers
• Detecting perfect powers in essentially linear time
• An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity
• Lacunaryx: computing bounded-degree factors of lacunary polynomials
• Computing the multilinear factors of lacunary polynomials without heights

Cites work

• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3785035 (Why is no real title available?)
• scientific article; zbMATH DE number 1305293 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 1504692 (Why is no real title available?)
• scientific article; zbMATH DE number 3049222 (Why is no real title available?)
• A polynomial time algorithm for diophantine equations in one variable
• An Inequality About Factors of Polynomials
• Approximate formulas for some functions of prime numbers
• Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some Applications
• Counting curves and their projections
• Detecting perfect powers in essentially linear time
• Early termination in sparse interpolation algorithms
• Factoring Polynomials over Algebraic Number Fields
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast construction of irreducible polynomials over finite fields
• Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
• Interpolation of polynomials given by straight-line programs
• New NP-hard and NP-complete polynomial and integer divisibility problems
• On Some Exponential Sums
• On fast multiplication of polynomials over arbitrary algebras
• On lacunary polynomial perfect powers
• On the number of terms of a composite polynomial
• On the number of terms of a power of a polynomial
• Polynomials whose powers are sparse
• Sieve algorithms for perfect power testing
• Sparse complex polynomials and polynomial reducibility
• Sparse squares of polynomials

Cited in

(5)

• An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity
• Randomized polynomial-time root counting in prime power rings
• Computing the multilinear factors of lacunary polynomials without heights
• Completing the L-th power in Z[x]
• On lacunary polynomial perfect powers

This page was built for publication: Detecting lacunary perfect powers and computing their roots

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650838)