Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Email: s.blackburn@rhul.ac.uk

Domingo Gomez-Perez
Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain
Email: gomezd@unican.es

Jaime Gutierrez
Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain
Email: jaime.gutierrez@unican.es

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, NSW 2109, Australia
Email: igor@comp.mq.edu.au

DOI: http://dx.doi.org/10.1090/S0025-5718-04-01698-9
PII: S 0025-5718(04)01698-9
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