Reconstructing noisy polynomial evaluation in residue rings

Let q>1 be an integer and let a and b be elements of the residue ring Zq of integers modulo q. We show how, when given a polynomial f∈Zq[X] and approximations to v0,v1∈Zq such that v1≡f(v0)modq one can recover v0 and v1 efficiently. This result has direct applications to predicting the polynomial congruential generator: a sequence (vn) of pseudorandom numbers defined by the relation vn+1≡f(vn)modq for some polynomial f∈Zq[X]. The applications lead to analogues of results known for the linear congruential generator xn+1≡axn+bmodq, although the results are much more restrictive due to nonlinearity of the problem.