Linear congruential PRNG

Have you ever wondered what kind of PRNG your calculator uses? Your Borland compiler? Your blackjack game? No? Well, chances are they use the same kind of PRNG:

Linear congruential pseudorandom number generator

The linear congruential (also known as linear congruent) PRNG is probably one of the most commonly used in programs, and one of a family of pseudorandom techniques known as Monte Carlo Techniques. It isn't used in any cryptographic software because it isn't cryptographically secure. The reason it's used is because it's easy to set up, and can look random, but it is actually predictable and easy to have a crack at. It generates numbers in the range (0...Z-1).

The reason it's known as the 'linear congruential' method is because at the heart of it lies this formula (part of which is of the form ax + c, hence the name):

X_n+1 = (A*X_n + C) mod Z

Here's how you make your 'random' numbers. First, you need to pick a seed (X₀), a multiplier (A), a modulus (Z) and a constant (C) to increment A*X_n. The modulus basically says what the range of the outputted list of numbers is; the output will be a list of numbers from 0 to Z-1. We can pick any value we like for X₀, A, Z and C, as long as four conditions are satisfied:

1. The increment C must be relatively prime to our modulus, Z.
2. A-1 must be a multiple of every prime p that divides Z.
3. A-1 must be a multiple of (a number) if Z is a multiple of (a number).
4. X₀, A, C and Z must all be greater than 0.

An example
Now I've explained what the LCPRNG is and how it works, let's use an example. I want to have a series of pseudorandom numbers from 1 to 16 inclusive. I've decided to use a LCPRNG. My modulus Z is going to be 16. According to the rules above, C must be relatively prime to Z and C > 0. A good choice for C would then be 3. Now we need to pick the multiplier A and the seed X₀. A-1 must be a multiple of every prime that divides into Z. Since only one prime number divides into Z, which is 2, A must be of the form 2n+1. In that case, A can be 5. The seed is independent and can be just about any integer (because the modulo operation makes it less than Z). In this case, let's use 9, just for convenience.

So, to sum up: X₀=9, A=5, Z=16 and C=3. Now let's get cracking.

X₁ = (5*9 + 3) mod 16 = 0
X₂ = (5*0 + 3) mod 16 = 3
X₃ = (5*3 + 3) mod 16 = 2
X₄ = (5*2 + 3) mod 16 = 13
X₅ = (5*13 + 3) mod 16 = 4
X₆ = (5*4 + 3) mod 16 = 7
X₇ = (5*7 + 3) mod 16 = 6
X₈ = (5*6 + 3) mod 16 = 1
X₉ = (5*1 + 3) mod 16 = 8
X₁₀ = (5*8 + 3) mod 16 = 11
X₁₁ = (5*11 + 3) mod 16 = 10
X₁₂ = (5*10 + 3) mod 16 = 5
X₁₃ = (5*5 + 3) mod 16 = 12
X₁₄ = (5*12 + 3) mod 16 = 15
X₁₅ = (5*15 + 3) mod 16 = 14
X₁₆ = (5*9 + 3) mod 16 = 9

Do you see how it works? The previously generated number is used as a 'seed' for the next number.
So, taking, X₁ to X₁₆, we get the numbers from 0 to 15 in this order: 0, 3, 2, 13, 4, 7, 6, 1, 8, 11, 10, 5, 12, 15, 14, 9. But I wanted numbers from 1 to 16, so we add them all by one to get:

1, 4, 3, 14, 5, 8, 7, 2, 9, 12, 11, 6, 13, 16, 15, 8

And that's my sequence of numbers. However, there are hints that the sequence isn't random. Look at (X₂, X₃), (X₆, X₇), (X₁₀, X₁₁) and (X₁₄, X₁₅).

Take note
If you don't follow the four rules I defined above, what can happen is that you end up with a sequence of numbers which does not contain all of the integers from 0 to Z. You may instead get a repeating sequence with a period smaller than Z, or you may get some negative numbers in your output.

In conclusion
It's easy to see why many trivial programs use the LCPRNG to generate random numbers. It's very easy to implement, easy to generate numbers you want (especially as it's a trivial matter to convert the numbers to binary) and easy to follow. If you use a very high modulus (we're talking something like 2³² or 2⁶⁴) and divide the output by it, you can get an impressive stream of fake random decimals. Here's a list of decimals from an LCPRNG I just cooked up myself.

.126465
.633057
.166016
.830811
.154785
.774658
.874023
.370850
.854980
.275635
.378906
.895264
.477051
.385986
.930664
.654053
.270996
.355713
.779297
.897217
.486816
.434814
.174805