Linear Congruential random number generators (LRNGs) are the simplest implementations of pseudo-random number generators used today. Since they require very little memory and are fast, they are ideal to be used in video game consoles. In fact, most video games rely on an implementation of this type of RNG to simulate random events.
A definition of an LRNG is the following:
Code:
x_{n+1} = (ax_n + c) mod m
where x_n is the n'th number of the sequence, m>0, 0<a<m and 0<=c<m. x_0, the seed value, is also a number between 0 and m-1. All the letters above are integers.
Thus, setting different values for a, c and m would result in a different LRNG. The period of an LRNG is the number of values generated in the sequence to start repeating the same numbers again. Most of the time, this is a number that is less than m. In certain cases, this is equal to m, in which case the LRNG is said to have a
full period. Here are the necessary and sufficient conditions to have a full period:
Property 1: c and m have no common factors.
Property 2: (a-1) is divisible by all the prime factors of m.
Property 3: If m is divisible by 4, then (a-1) is divisible by 4.
A Simple LRNG
Let's provide a simple example of an LRNG that has full period. Since we need that (a-1) be divisible by all the prime factors of m, from property 2 above, we define m to be a power of 2, so that 2 would be the only prime factor of m. For the sake of simplicity, we set m = 16. From property 2 again, we now need (a-1) to be divisible by 2, i.e. we need it to be an odd number. Let's set it, arbitrarily, to 5. Property 1 requires that c and m have no common factors. This means that c must be an odd number also, so we set it arbitrarily to 9. Finally, property 3 tells us that if m is divisible by 4 (which it is), then (a-1) must also be divisible by 4. In this case, we chose a = 5, and 5-1 is divisible by 4, so we're set.
So our little LRNG is:
Code:
x_{n+1} = (5x_n + 9) mod 16
Here is the output of this particular LRNG, starting from x_0 = 0:
Code:
0, 9, 6, 7, 12, 5, 2, 3, 8, 1, 14, 15, 4, 13, 10, 11, 0, 9, 6, ...
As can be confirmed immediately, the above LRNG has period 16, the maximum possible period. The numbers don't look like they are very random, but this is to be expected since there are only 16 possible values for each random number. If we wanted a better RNG, we'd want the random numbers to have a much larger range, and this is what games usually do.
Practical Implementations
Most games console LRNG implementations make m a big power of 2. This has two advantages. The first one is that it is relatively easy to find all its prime factors, as we did above. The second advantage is that finding the modulo of a power of 2 is very simple for a games machine that works in binary. Unfortunately, this also leads to some limitations. For one, the numbers generated will, invariably, be alternatingly even and odd. (For example, look at the above output.) To circumvent this problem, most LRNGs usually output only the first few significant bits of x_n instead of the whole number. This is because it can be shown that the least significant bits have a far shorter period than the most significant ones.
Thus, most implementations use 2^32 or 2^64 for the value of m, and then output the first half of the bits of x_n. This is the approach used by the Pokemon RNG. In fact, in the Pokemon RNG (PRNG), a = 1103515245, c = 24691 and m = 2^32, and the first 16 bits are output from x_n. You can also see that these numbers satisfy the three properties listed above, and hence the PRNG has full period.
Reversing a full-period LRNG
Suppose we wish to reverse the output of a full-period LRNG. One way of doing this is to call the LRNG (m-1) times instead of once. Since the LRNG has period m, calling it (m-1) would result in the previous random number. (See the previous simple example to confirm this.) This, however, is very inefficient, especially if the value of m is large, as it invariably is. We thus want to find a much more efficient method.
Henceforth we'll assume that the LRNG has full period, i.e. properties 1, 2 and 3 above hold. We shall also assume that m = 2^k for some positive integer m.
We start from
Code:
x_{n+1} = (ax_n + c) mod m ...[1]
the normal definition for an LRNG. We want to ideally find two numbers A and C such that
Code:
x_n = (Ax_{n+1} + C) mod m ...[2]
i.e. two numbers A and C so that they provide the reverse output of the LRNG. We first provide the following lemmas:
Lemma 1: If [1] and [2] hold, then aA = 1 mod m and aC = -c mod m.
Proof: Suppose (Ax_{n+1} + C) mod m is some number y. We show that if A and C satisfy the above properties, then y = x_n, the previous output from the LRNG.
Code:
y = (Ax_{n+1} + C) mod m
Multiplying both sides by a, we get
Code:
ay = a(Ax_{n+1} + C) mod m
ay = (aAx_{n+1} + aC) mod m
But aA = 1 mod m, and hence aAx_{n+1} = x_{n+1} mod m. Also, aC = -c mod m. So we have:
Code:
ay = (x_{n+1} - c) mod m
ay + c = x_{n+1} mod m ...[3]
Comparing [3] with [1], we find that y = x_n, as required.
[]
Thus A is the number such that, when multiplied by a, the result is 1 mod m. In such a case, A is called the multiplicative inverse of a. Also C is the number such that, when multiplied by a, the result is -c mod m.
We now need Lemma 2, which will be useful later on.
Lemma 2: If the LRNG has full period, then a and m have no common factors.
Proof: Since the LRNG has full period, in particular property 2 holds, i.e. (a-1) is divisible by all the prime factors of m. By the
fundamental theorem of arithmetic, m can be decomposed into its unique factorisation of prime numbers, i.e. m = p_1^k_1 p_2^k_2 ... p_n^k_n, where p_i is a distinct prime and k_i is a positive integer for all 1<=i<=n. Since (a-1) is divisible by all the primes of m, then we have:
Code:
a-1 = r_1p_1 = r_2p_2 = r_3p_3 = ... = r_np_n for appropriate r_i's.
a-1 = r_ip_i for all 1<=i<=n
a = r_ip_i + 1 for all 1<=i<=n
a = 1 mod p_i for all 1<=i<=n
Thus we note that a is not divisible by any prime factor of m. Hence a and m have no common factors, as required.
[]
We now define Euler's phi function as:
Code:
phi(n) is the number of positive integers k<=n that have no common factors with n.
It is easy to show that if p is a prime number, then phi(p) = p-1. The following lemma says more:
Lemma 3: If p is a prime number, then phi(p^n) = (p-1)p^{n-1}.
Proof: The numbers less than p^n that have a common factor with p^n are p, 2p, 3p, ... p^n. Hence there are p^{n-1} numbers having a common factor with p^n, so those that don't have a common factor are the remaining numbers, of which there are p^n - p^{n-1} = p^{n-1}(p-1), as required.
[]
Furthermore, we quote, without proof,
Fermat's Little Theorem:
Theorem (Fermat): If p is a prime number and a and p have no common factors, then a^{p-1} = 1 mod p.
[]
Here is a corollary to Fermat's Little Theorem:
Corollary 1: If a and m have no common factors, then a^{phi(m)} = 1 mod m.
Proof: Take all the distinct positive integers b_1, b_2, ... b_n<=m that have no common factors with m, where n=phi(m). Consider the multiples ab_1 mod m, ab_2 mod m, ...,ab_n mod m. All of these multiples are different, since suppose ab_i = ab_j mod m for some i and j. Since a and m have no common factors, we can cancel out, giving b_i = b_j mod m, which contradicts the fact that all the b_i's are distinct for all i.
Furthermore, each number ab_i does not have any common factor with m since a and b_i both don't have any common factor with m. Therefore, these n different numbers
ab_1 mod m, ab_2 mod m, ...,ab_n mod m
are the n different numbers that don't have any common factors with m. Hence, each of them is equal to one of b_1, b_2, ... b_n.
Hence,
(ab_1)(ab_2)...(ab_n) = b_1b_2...b_n mod m
Since all of the b_i's above do not have any common factor with m, we can cancel each of them from both sides, giving
a.a...a = 1 mod m
There are n a's in the above equation, and n = phi(m), and hence a^{phi(m)} = 1 mod m, as required.
[]
Finally, we get to our second corollary.
Corollary 2: If ax = b mod m and a and m have no common factors, then x = ba^{phi(m)-1} mod m.
Proof: We start with
Multiplying both sides by a^{phi(m)-1}, we get
Code:
a.a^{phi(m)-1}.x = b.a^{phi(m)-1} mod m
a^{phi(m)}.x = b.a^{phi(m)-1} mod m
Since a and m have no common factors, a^{phi(m)} = 1 mod m by Corollary 1. Hence we have:
Code:
x = b.a^{phi(m)-1} mod m
as required.
[]
Corollary 2 and Lemma 3 allows us to find A and C in the formula that reverses the output of a full-period LRNG:
Proposition: If x_{n+1} = (ax_n + c) mod m is a full-period LRNG and m = 2^k, then x_{n+1} = (Ax_n + C) mod m provides the reverse output of the first LRNG if A = a^{(m-2)/2} mod m and C = -cA mod m.
Proof: From Lemma 1, we have that aA = 1 mod m. Since a and m do not have common factors by Lemma 2, we can apply Corollary 2 to solve for A:
Code:
A = 1.a^{phi(m)-1} mod m
Since m=2^k, phi(m) = phi(2^k) = (2-1)2^{k-1} = 2^{k-1} = m/2 by Lemma 3. Hence,
Code:
A = a^{m/2-1} = a^{(m-2)/2} mod m
Again from Lemma 1, we have that aC = -c mod m. We can thus apply Corollary 2 again to get:
Code:
C = -c.a^{phi(m)-1} mod m
Again the power of a here is (m-2)/2, so we have
Code:
C = -c.a^{m/2-1} mod m
C = -cA mod m
as required.
[]
A Small Example
Let us reverse the small LRNG we defined at the start as an example of how to apply the above proposition.
Our LRNG was defined by x_{n+1} = (5x_n + 9) mod 16. Hence, a=5, c=9 and m=16=2^4.
By the above proposition, the LRNG that has the reverse output of the above LRNG has
A = 5^{(16-2)/2} mod 16 = 5^7 mod 16 = 78125 mod 16 =
13.
and
C = -9*13 mod 16 = -117 mod 16 =
11.
Hence the LRNG
x_{n+1} = (13x_n + 11) mod 16 should provide the reverse output of x_{n+1} = (5x_n + 9) mod 16. Indeed, its output is, starting from x_0 = 0:
0, 11, 10, 13, 4, 15, ...
A Small Problem
The problem with the above method of finding A and C (especially of finding A) is that, if a and m are very large numbers, the calculation for A might require too much memory to do. Indeed, if we were to reverse the Pokemon RNG itself:
Code:
x_{n+1} = 1103515245x_n + 24691 mod 2^32
we would need to find A by calculating 1103515245^2147483647 mod 4294967296, which requires the biggest of calculators to evaluate.
Fortunately, help is at hand, from the so-called Euclid's Extended GCD Algorithm.
Euclid's Extended GCD Algorithm
In his book
Elements, Euclid, a Greek mathematician living in circa 300BC, provides an algorithm to find the greatest common divisor (GCD) of two numbers, and a rather efficient one at that. This algorithm was then extended to provide not just the GCD of two numbers, but the two numbers x and y such that
We note that if a and b do not have common factors, then their GCD is 1. Hence we have:
ax + by = 1 if a and b have no common factors.
Thus we have
ax = 1 mod b
by = 1 mod a
and hence Euclid's Extended GCD Algorithm (EEGA) allows us to solve the equation
aA = 1 mod m
in a more efficient way for full-period LRNGs.
The algorithm can be defined recursively as follows:
Code:
EEGA takes (a,b) as input and outputs the pair (x,y).
EEGA(a,b) = (0,1), if a mod b = 0
EEGA(a,b) = (g,f-g*(a div b)), otherwise, where (f,g) = EEGA(b,a mod b)
a div b is the quotient of a/b, while a mod b is the remainder of a/b.
Two Examples
Example 1:
Reversing our simple LRNG using the EEGA
Our simple LRNG was
Code:
x_{n+1} = (5x_n + 9) mod 16
Here we have a = 5, c = 9, m = 16. To reverse the RNG, we want A and C such that
Aa = 1 mod m, C = -cA mod m.
To solve Aa = 1 mod m, we resort to the EEGA.
Code:
EGA(16,5) = (g,f-g*(16 div 5)) where (f,g) = EEGA(5, 16 mod 5)
16 div 5 = 3, 16 mod 5 = 1.
EEGA(5,1) = (0,1)
Hence EEGA(16,5) = (1,0-1*3) = (1,-3).
Thus we get x = 1, y = -3. Now since
16x + 5y = 1
we have that
5y = 1 mod 16
and hence the output for y is equal to our required A. Hence
y = -3 mod 16 =
13, as before.
Now
C = -cA mod m
C = (-9 * 13) mod 16 =
11, as before.
Hence the LRNG
Code:
x_{n+1} = (13x_n + 11) mod 16
provides the reverse output of our little LRNG.
Example 2:
Reversing the Pokemon RNG using the EEGA
The Pokemon RNG (PRNG) is:
Code:
x_{n+1} = (1103515245x_n + 24691) mod 2^32
Hence we have a = 1103515245, c = 24691, m = 2^32 = 4294967296.
To reverse the RNG, we want A and C such that
Aa = 1 mod m, C = -cA mod m.
To solve Aa = 1 mod m, we resort to the EEGA.
Code:
EEGA(4294967296,1103515245) = (g,f-g*(4294967296 div 1103515245)) where (f,g) = EEGA(1103515245,4294967296 mod 1103515245)
4294967296 div 1103515245 = 3, 4294967296 mod 1103515245 = 984421561
EEGA(1103515245,984421561) = (g,f-g*(1103515245 div 984421561)) where (f,g) = EEGA(984421561,1103515245 mod 984421561)
1103515245 div 984421561 = 1, 1103515245 mod 984421561 = 119093684
EEGA(984421561,119093684) = (g,f-g*(984421561 div 119093684)) where (f,g) = EEGA(119093684,984421561 mod 119093684)
984421561 div 119093684 = 8, 984421561 mod 119093684 = 31672089
EEGA(119093684,31672089) = (g,f-g*(119093684 div 31672089)) where (f,g) = EEGA(31672089,119093684 mod 31672089)
119093684 div 31672089 = 3, 119093684 mod 31672089 = 24077417
.
.
.
EEGA(15,14) = (g,f-g*(15 div 14)) where (f,g) = EEGA(14,15 mod 14)
15 div 14 = 1, 15 mod 14 = 1
EEGA(14,1) = (0,1).
After 22 recursive calls, EEGA finds its base case, and after unwinding, it returns the pair
(74460346,-289805467)
Thus we get x = 74460346, y = -289805467. Now since
4294967296x + 1103515245y = 1
we have that
1103515245y = 1 mod 4294967296
and hence the output for y is equal to our required A. Hence
A = -289805467 mod 2^32 =
4005161829.
Now
C = -cA mod m
C = (-24691 * 4005161829) mod 2^32
C = -98891450719839 mod 2^32
C = -4123696735 mod 2^32
C =
171270561.
Hence the LRNG
Code:
x_{n+1} = (4005161829x_n + 171270561) mod 2^32
provides the reverse output of the Pokemon RNG.