| TR#: | CS0533 |
| Class: | CS |
| Title: | How to Predict Congruential Generators |
| Authors: | Hugo Krawczyk |
| CS0533.pdf | |
| Abstract: | In this paper we show how to predict a large class of pseudorandom number generators. Namely, generators outputting a sequence of integers sO,sl,... where Si is computed by the recurrence Si==???(mod m) for integers m and aj, and integer functions ???. Our predictors are efficient, provided that the functions ??? are computable (over the integers) in polynomial time. These predictors have access to the elements of the sequence prior to the element being predicted, but they do not know the modulus m, nor the coefficients ai the generalor actually works with. This extends previous results about the predictability of such generators, In particular, we prove the predictability of multivariate polynomial generators, i.e. generators where Si==???(mod m), for a polynomial P of fixed degree in n variables. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1988/CS/CS0533), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1988
To the main CS technical reports page