While many may consider encryption to be necessary only for top-secret high level communications, they are increasingly widely used in a variety of purposes, such as encrypting sensitive information sent through web browsers; such as bank details! Most encryption algorithms used to encrypt these information (eg. ) are most effective when they make use of long, random sequence of numbers (ie. they have high entropy). 

Additionally, we would want our random numbers to be secure – ie. they are not biased towards a certain range, making them hard to guess. This is also known as uniformity as each and every number (inclusively in a series) has an equal chance of being chosen.

Linear Congruential Methods (LCM) / Generators

History: The main idea behind the LCM is the Recurrence relation

A recurrence relation is a way of expressing each element of a sequence as a function of the previous ones

This is also related to the idea of recursion – a concept that solves a problem by solving a smaller version of itself each time. For a recursion to occur, there must be a base or terminating case, and defined in terms of calling itself.

The linear congruential generator is defined by the equation below:

X_{n+1} = \left( a X_n + c \right)\bmod m

  • X_n refers to a random number (consisting of a long random sequence of numbers)
  • X_{n+1} refers to the next term in the series (in this case, the output of the equation i.e, the random number) 
  • m , where 0 < m , the modulus
  • a , where 0 < a < m, the multiplier
  • c,\,0 \le c < m, where c is the increment
  • X_{n=0},\,0 \le X_0 < m which is the starting (aka “seed”) value

Observations: We realise that the power of the largest variable X_n is 1, indicating that this is a first degree polynomial. This is known as a linear recurrence relation.

According to the equation, we realise that the formula continuously cycles between 0 and m-1. We can demonstrate this through the use of a trace program (useful for exploring recursive cases). First, let’s create a function LinearCongruentialGenerator based on the formula above.

				
					data class VarNums(val a: Int, var seed:Int, val c:Int, val modulus:Int)

fun LinearCongruentialGenerator(vn: VarNums) {
    var count = 0
    while (count \&lt; vn.modulus) {
        vn.seed = (vn.a * vn.seed + vn.c) % vn.modulus
        count++
        println(vn.seed)
    }
}

LinearCongruentialGenerator((VarNums(23,12,17,37)))
				
			
				
					
3
28
23
24
18
25
12
3
28
23
24
18
25
12
3
28
23
24
18
25
12
3
28
23
24
18
25
12
3
				
			

Notice that the numbers seem to be random at first (3, 28, 23…) and then they repeat. This is known as the period of the function. This period is important as it dictates how long an algorithm can continue to churn out unique sequences of numbers before returning to the first value in a sequence, as this affects the viability of the “pseudo” random number generator.

A popular adaptation of the LCM is the Lehmer random number generator. It sets m, the modulus to a prime number (or multiples of it), and sets the increment to 0. Most importantly, the initial seed X_0 must be coprime to the modulus m which is not required for other Linear Congruential generators

What is co-prime?

Co-prime describe a relationship between 2 numbers whereby the only common positive integer that divides them (aka, greatest common divisor) is 1. Notice in the image how the line does not intersect at any other point​

To maximise the period, we need to carefully pick the parameters. One such approach (known as the Hull-Dobell Theorem) is detailed below:

1. m the modulus and c the increment have to be co-prime
2. a – 1 is divisible by all prime factors of m the modulus
3. a – 1 is divisible by 4 if m is divisible by 4

To further maximise the period, we can also combine several LCGs together. We will not go into detail on this but feel free to read further!

				
					interface Seedable {
    /**
        * Seed the random number/vector/scenario generator to produce repeatable
        experiments.
        *
        * @param seeds the seeds
        */
    fun seed(seeds) {
        return
    }
}

interface RandomNumberGenerator:Seedable {
    /**
    * Get the next random {@code double}.
    *
    * @return the next random number
    */
    fun nextDouble();
}
				
			

Now, let us generate a list of random numbers using two other RNG algorithms , Lecuyer RNG (a non-linear RNG method) and composite RNG (a linear RNG method).

Notice that the LCGs produce an identical set of integers. To sample from the distribution, they scale integers to within the same unit interval.

Now, let us use another common algorithm, Mersenne Twister. It had a vastly longer period of 219937 -1 is much more than 232 of the Linear Congruential Methods. Thus, it is one of the most widely used.

We can make use of kotlin to measure the time needed.

				
					var rng = MersenneTwister()
val startTime: Long = System.nanoTime()
val N: Int = 1000000
for (i in 0..N) {
    rng.nextDouble()
} 
val endTime: Long = System.nanoTime()
val duration: Long = (endTime-startTime)
val ms: Double = duration.toDouble()/1000000
println("took MT19937 %f milliseconds to generate %d random numbers".format(ms, N))
				
			
				
					&gt;&gt; took MT19937 55.941550 milliseconds to generate 1000000 random numbers
				
			

Thinking time: Contrast this with the time needed for the Lehmer generator.

Which is shorter? 🤔