A polynomial time algorithm for diophantine equations in one variable.

Felipe Cucker (1) , Pascal Koiran (1) , Steve Smale (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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).

On montre que les racines entières d'un polynôme en une variable à coefficients entiers peuvent être calculées en temps polynomial. Ce résultat est valable pour le modèle de calcul classique des machines de Turing et pour une représentation creuse des polynômes (coefficients et exposants sont écrits en binaire, et seuls les monômes non nul sont représentés).

Mots clés: Computer Algebra; Diophantine Equations; Sparse Polynomials

Mots clés: Calcul Formel; Equations Diophantiennes; Polynômes Creux

Domaines: Informatique [cs]

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⟩