A polynomial time algorithm for diophantine equations in one variable.

Abstract : We show that the integer roots of of a univariate polynomial with integer coefficients can be computed in polynomial time. This result holds for the classical (i.e. Turing) model of computation and a sparse representation of polynomials (i.e. coefficients and exponents are written in binary, and only nonzero monomials are represented).
Document type :
Reports
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102070
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:13:31 AM
Last modification on : Saturday, May 4, 2019 - 1:26:36 AM

File

RR1997-45.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102070, version 1

Collections

Citation

Felipe Cucker, Pascal Koiran, Steve Smale. A polynomial time algorithm for diophantine equations in one variable.. [Research Report] LIP RR-1997-45, Laboratoire de l'informatique du parallélisme. 1997, 2+10p. ⟨hal-02102070⟩

Share

Metrics

Record views

10

Files downloads

48