Name
Abstract | ||
|---|---|---|
Let p be a prime and let a and b be elements of the finite field 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) = au(n)(-1n) +b modp. 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 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) = f(v(n)) mod p, where f is an element of 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) = ax(n) + 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1090/S0025-5718-04-01698-9 | MATHEMATICS OF COMPUTATION |
Keywords | Field | DocType |
finite field,pseudorandom number generator | Prime (order theory),Finite field,Mod,Combinatorics,Linear congruential generator,Quadratic equation,Random number generation,Mathematics,Pseudorandom number generator,Inversive congruential generator | Journal |
Volume | Issue | ISSN |
74 | 251 | 0025-5718 |
Citations | PageRank | References |
23 | 1.16 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simon R. Blackburn | 1 | 357 | 36.95 |
| Domingo Gomez-perez | 2 | 61 | 10.22 |
| Jaime Gutierrez | 3 | 154 | 18.15 |
| Igor E. Shparlinski | 4 | 1339 | 164.66 |