Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Predicting nonlinear pseudorandom number generators

Authors: Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez and Igor E. Shparlinski
Journal: Math. Comp. 74 (2005), 1471-1494
MSC (2000): Primary 11H06, 11K45, 11T71, 94A60
Published electronically: July 27, 2004
MathSciNet review: 2137013
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $p$ be a prime and let $a$ and $b$ be elements of the finite field $\mathbb {F}_p$ of $p$ elements. The inversive congruential generator (ICG) is a sequence $(u_n)$ of pseudorandom numbers defined by the relation $u_{n+1} \equiv a u_n^{-1} + b \bmod p$. We show that if sufficiently many of the most significant bits of several consecutive values $u_n$ of the ICG are given, one can recover the initial value $u_0$ (even in the case where the coefficients $a$ and $b$ are not known). We also obtain similar results for the quadratic congruential generator (QCG), $v_{n+1} \equiv f(v_n) \bmod p$, where $f \in \mathbb {F}_p[X]$. This suggests that for cryptographic applications ICG and QCG should be used with great care. Our results are somewhat similar to those known for the linear congruential generator (LCG), $x_{n+1} \equiv a x_n + b \bmod p$, but they apply only to much longer bit strings. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for LCG.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11H06, 11K45, 11T71, 94A60

Retrieve articles in all journals with MSC (2000): 11H06, 11K45, 11T71, 94A60

Additional Information

Simon R. Blackburn
Affiliation: Department of Mathematics, Royal Holloway, University of London, Egham, Surrey, TW20 0EX, United Kingdom

Domingo Gomez-Perez
Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain

Jaime Gutierrez
Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, NSW 2109, Australia
MR Author ID: 192194

Received by editor(s): August 14, 2003
Received by editor(s) in revised form: February 6, 2004
Published electronically: July 27, 2004
Article copyright: © Copyright 2004 American Mathematical Society