Jan
11
2006
More Randomness
It turns out that the “random number generator” I wrote about previously is a special case of a “Linear-Congruential Pseudo-Random Number Generator”. These are the de-facto method of generating repeatable random-like sequences of numbers. They take the form:
SEED = ( A * SEED + C ) mod M
The maximum length of a sequence generated by this algorithm is M, and is given when the following conditions are met:
1) C and M share no common factors other than 1.
2) A - 1 is a multiple of every prime factor of M.
3) A - 1 is a multiple of 4, if M is a multiple of 4.
A proof of this is given by Donald Knuth in “The Art Of Computer Programming: Vol 2. Seminumerical Algorithms”
Information taken from:
http://world.std.com/~franl/crypto/random-numbers.html
