A polynomial time algorithm for diophantine equations in one variable

DOI10.1006/jsco.1998.0242zbMath0920.11085OpenAlexW1980469175MaRDI QIDQ1284218

Felipe Cucker, Pascal Koiran, Stephen Smale

Publication date: 20 June 1999

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

Full work available at URL: https://semanticscholar.org/paper/2a08fb87f8e8e368322bdf1e65245b5bcabc74c7

zbMATH Keywords

roots of polynomialscomplexity theorysparse polynomialsdiophantine equations in one variable

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computer solution of Diophantine equations (11Y50) Number-theoretic algorithms; complexity (11Y16) Higher degree equations; Fermat's equation (11D41)

Related Items (14)

Bounded-degree factors of lacunary multivariate polynomials ⋮ Factoring bivariate sparse (lacunary) polynomials ⋮ A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum ⋮ Lacunaryx ⋮ Detecting lacunary perfect powers and computing their roots ⋮ Sparse bivariate polynomial factorization ⋮ Root refinement for real polynomials using quadratic interval refinement ⋮ Computing the multilinear factors of lacunary polynomials without heights ⋮ Root separation for trinomials ⋮ Reachability problems in low-dimensional nondeterministic polynomial maps over integers ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields ⋮ The number of roots of a lacunary bivariate polynomial on a line ⋮ Mathematical problems for the next century ⋮ Some speed-ups and speed limits for real algebraic geometry

This page was built for publication: A polynomial time algorithm for diophantine equations in one variable