If you check 0, 1, -1, 2, -2..., then you are not using any certificate. An obvious idea is to use the root of the polynomial as a certificate.

Now we need to show that the maximal root has polynomial size compared to the polynomial. One way to do this is to use the following necessary condition for a number to be a root. If ( ) has an integer root, then this root divides . It is easy to show this. (In fact, there is a more general fact about rational roots; the first place I found it is in this PDF file, p. 4.)

As an unrelated aside, note that if we consider polynomials with arbitrary number of variables and integer coefficients, then the problem of finding out whether a given polynomial has an integer root is undecidable (Hilbert's tenth problem).