TY - JOUR

T1 - Predicting nonlinear pseudorandom number generators

AU - Blackburn, Simon R.

AU - Gomez-Perez, Domingo

AU - Gutierrez, Jaime

AU - Shparlinski, Igor E.

N1 - 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.

PY - 2005/7

Y1 - 2005/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=21644470546&partnerID=8YFLogxK

U2 - 10.1090/S0025-5718-04-01698-9

DO - 10.1090/S0025-5718-04-01698-9

M3 - Article

AN - SCOPUS:21644470546

VL - 74

SP - 1471

EP - 1494

JO - Mathematics of Computation

JF - Mathematics of Computation

SN - 0025-5718

IS - 251

ER -