A polynomial time algorithm for diophantine equations in one variable. - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

A polynomial time algorithm for diophantine equations in one variable.

Résumé

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).
Fichier principal
Vignette du fichier
RR1997-45.pdf (215.89 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102070 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102070 , version 1

Citer

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⟩
7 Consultations
156 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More