## Abstract

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_{0}, v_{1} ∈ Z_{q} such that v_{1} ≡ f (v_{0}) mod q one can recover v_{0} and v_{1} 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.

Original language | English |
---|---|

Pages (from-to) | 47-59 |

Number of pages | 13 |

Journal | Journal of Algorithms |

Volume | 61 |

Issue number | 2 |

DOIs | |

Publication status | Published - Nov 2006 |