A polynomial time algorithm for diophantine equations in one variable (Q1284218)

The goal of this paper is to prove that there is a polynomial time algorithm which given input \(f\in {\mathbb Z}[X]\) outputs the set of integer roots of \(f\). The authors choose a sparse representation of polynomials and define the size of polynomials with respect to this encoding. The main step is to find an algorithm (of polynomial cost) to compute the sign of \(f(x)\) for a given integer \(x\). The key lemma used by the authors is the following: There is an algorithm which given \((x,\alpha)\in {\mathbb N}^2\), \(x>0\), outputs \(\ell\in {\mathbb N}\) such that \(2^{\ell-1}\leq x^\alpha \leq 2^{\ell+1}\); the halting time being bounded by a polynomial in the size of \(x\) and of \(\alpha\). The proof of this lemma is based on a theorem of Brent concerning the computation of the first digits of \(\log x\). The paper ends with several interesting open problems.