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:

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:

Here is the output of this particular LRNG, starting from x_0 = 0:

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

the normal definition for an LRNG. We want to ideally find two numbers A and C such that

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.

Multiplying both sides by a, we get

But aA = 1 mod m, and hence aAx_{n+1} = x_{n+1} mod m. Also, aC = -c mod m. So we have:

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:

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:

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

Since a and m have no common factors, a^{phi(m)} = 1 mod m by Corollary 1. Hence we have:

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:

Since m=2^k, phi(m) = phi(2^k) = (2-1)2^{k-1} = 2^{k-1} = m/2 by Lemma 3. Hence,

Again from Lemma 1, we have that aC = -c mod m. We can thus apply Corollary 2 again to get:

Again the power of a here is (m-2)/2, so we have

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:

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:

Two Examples

Example 1: Reversing our simple LRNG using the EEGA

Our simple LRNG was

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.

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

provides the reverse output of our little LRNG.

Example 2: Reversing the Pokemon RNG using the EEGA

The Pokemon RNG (PRNG) is:

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.

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

provides the reverse output of the Pokemon RNG.

Thanks for writing this essay. I was curious about how you had reversed the pokemon RNG and the relevant theory.

Wow. That is all I can say.