
Glossary: Prime Pages: Top 5000: 
Computer programs can not generate truly random numbers,
but they often do generate lists of numbers that "look"
random (these lists, or sequences, are called
pseudorandom). One of the most common ways to
do this is to use a linear congruential sequence.
To create such a sequence we first choose four numbers:
X_{n+1} = aX_{n}+c (mod m).For example, let m=17, a=3, c=11 and X_{0}=0. Then we get the sequence: 0, 11, 10, 7, 15, 5, 9, 4, 6, 12, 13, 16, 8, 1, 14, 2, 0 (now the sequence repeats).With m=37, a=24, c=17 and X_{0}=0, we get the sequence: 0, 17, 18, 5, 26, 12, 9, 11, 22, 27, 36, 30, 34, 19, 29, 10, 35, 6, 13, 33, 32, 8, 24, 1, 4, 2, 28, 23, 14, 20, 16, 31, 21, 3, 15, 7, 0, (now the sequence repeats).Some computer programs and calculators use a large prime for the modulus to form such a sequence, and then divide each number in the sequence by that prime to return a "random" number between 0 and 1. But we must be careful! With m=37, a=26, c=17 and X_{0}=0 we get the sequence 0, 17, 15, 0 (now the sequence repeats)So how do we avoid a short sequence? One way is to choose c relatively prime to m and make sure every prime divisor of m also divides a1 (and if 4 divides m, that 4 divides a1); then the sequence has length m. When we let m be a prime and set c to zero, we need to let a be a primitive root modulo p. Chapter three of Knuth's text (see below) is an extensive and excellent (but highly technical) reference on pseudorandom number generators and how to measure randomness. Let us end with the quote he begins with. Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. (John von Neumann, 1951)
References:
Chris K. Caldwell © 19992017 (all rights reserved)
