Reconstructing noisy polynomial evaluation in residue rings

Let q > 1 be an integer and let a and b be elements of the residue ring Z_q of integers modulo q. We show how, when given a polynomial f ∈ Z_q [X] and approximations to v₀, v₁ ∈ Z_q such that v₁ ≡ f (v₀) mod q one can recover v₀ and v₁ efficiently. This result has direct applications to predicting the polynomial congruential generator: a sequence (v_n) of pseudorandom numbers defined by the relation v_{n + 1} ≡ f (v_n) mod q for some polynomial f ∈ Z_q [X]. The applications lead to analogues of results known for the linear congruential generator x_{n + 1} ≡ a x_n + b mod q, although the results are much more restrictive due to nonlinearity of the problem.