Linear Congruential Generators Do Not Produce Random Sequences
- 25 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 480-484
- https://doi.org/10.1109/sfcs.1984.715950
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.Keywords
This publication has 7 references indexed in Scilit:
- Integer Programming with a Fixed Number of VariablesMathematics of Operations Research, 1983
- An overview of computational complexityCommunications of the ACM, 1983
- Improved algorithms for integer programming and related lattice problemsPublished by Association for Computing Machinery (ACM) ,1983
- Theory and application of trapdoor functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Inferring a sequence generated by a linear congruencePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- How to generate cryptographically strong sequences of pseudo random bitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- “CRACKING” A RANDOM NUMBER GENERATORCryptologia, 1977