Let p p be a prime and F p \mathbb {F}_p the finite field with p p elements. We show how, when given an irreducible bivariate polynomial F ∈ F p [ X , Y ] F \in \mathbb {F}_p[X,Y] and an approximation to a zero, one can recover the root efficiently, if the approximation is good enough. The strategy can be generalized to polynomials in the variables X 1 , … , X m X_1,\ldots ,X_m over the field F p \mathbb {F}_p . These results have been motivated by the predictability problem for nonlinear pseudorandom number generators and other potential applications to cryptography.