Predicting nonlinear pseudorandom number generators

Simon R. Blackburn*, Domingo Gomez-Perez, Jaime Gutierrez, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)
7 Downloads (Pure)

Abstract

Let p be a prime and let a and b be elements of the finite field double-struck F signp of p elements. The inversive congruential generator (ICG) is a sequence (un) of pseudorandom numbers defined by the relation un+1 = aun-1 + b mod p. We show that if sufficiently many of the most significant bits of several consecutive values un of the ICG are given, one can recover the initial value U0 (even in the case where the coefficients a and b are not known). We also obtain similar results for the quadratic congruential generator (QCG), vn+1 = f(vn) mod p, where f ∈ double-struck F signp[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), xn+1 = axn + b mod 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.

Original languageEnglish
Pages (from-to)1471-1494
Number of pages24
JournalMathematics of Computation
Volume74
Issue number251
DOIs
Publication statusPublished - Jul 2005

Bibliographical note

Copyright [2005] American Mathematical Society. First published in Mathematics of Computation, 74:251, published by the American Mathematical Society. The original article can be found at http://www.ams.org/journals/mcom/2005-74-251/S0025-5718-04-01698-9/S0025-5718-04-01698-9.pdf.

Fingerprint Dive into the research topics of 'Predicting nonlinear pseudorandom number generators'. Together they form a unique fingerprint.

Cite this