An algorithm for computing the integer roots of a polynomial in onevariable with integer coefficients is presented. The goal of the paperis the proof of the following theorem: “There is a polynomial timealgorithm which given a function f, of one variable over the integers, decides whetherf has an integer root and, moreover, the algorithmoutputs the set of integer roots of f.” The algorithm relies on anefficient procedure for evaluating the sign of f at a given integer.