Abstract | ||
---|---|---|
One of the most popular and fast methods of generating "random" sequence are linear congruential generators. This paper discusses the predictability of the sequence given only a constant proportion /spl alpha/ of the leading bits of the first few numbers generated. We show that the rest of the sequence is predictable in polynomial time, almost always, provided /spl alpha/ 2/5. |
Year | DOI | Venue |
---|---|---|
1984 | 10.1109/SFCS.1984.715950 | FOCS |
Keywords | Field | DocType |
constant proportion,linear congruential generators,linear congruential generator,spl alpha,fast method,random sequences,polynomial time,leading bit,polynomials,random sequence,random number generation,computer science,testing,cryptography | Discrete mathematics,Random element,Combinatorics,Random graph,Multiply-with-carry,Random number table,Random permutation,Random number generation,Mathematics,Random function,Pseudorandom number generator | Conference |
ISBN | Citations | PageRank |
0-8186-0591-X | 14 | 38.92 |
References | Authors | |
6 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
A. M. Frieze | 1 | 748 | 193.55 |
Ravindran Kannan | 2 | 3893 | 850.76 |
J. C. Lagarias | 3 | 563 | 235.61 |