Implementing A Pseudorandom Number Generator In Python From Scratch
Learn to implement Linear Congruential Generator (LCG), a pseudorandom number generator in Python
Computers use deterministic algorithms to generate Pseudorandom numbers.
These algorithms called Pseudorandom number generators (PRNGs) take a seed value and return a Pseudo-random number.
Let’s talk about one of such popular algorithms.
Note that true randomness is usually generated by Hardware Random Number Generators (HRNGs)/ environmental noise/ quantum processes etc. These are not discussed in this article.
The Linear Congruential Generator (LCG)
This is one of the simplest and most popular algorithms for generating pseudorandom numbers.
Its mathematical simplicity makes it ideal to be deployed on microcontrollers/ embedded systems with low processing capabilities.
The generator is defined by the following equation:
where:
X(n)is the current pseudorandom number in the sequenceX(n+1)is the next pseudorandom number in the sequencea(multiplier constant),c(increment constant) andm, are constants used to control the generator’s behaviourmodis the modulo operation, which gives the remainder of the division
Period of LCG
The period of an LCG is the number of unique values the generator can produce before it starts repeating itself.
With a full period, the LCG can generate all possible values in its range before repeating.
An LCG is called full-period if its period is equal to m.
An LCG has a full period only if the following holds:
candmare co-prime (have no common factors other than 1)a — 1is divisible by all prime factors ofma — 1is a multiple of 4 ifmis a multiple of 4
LCG At Work
To start an initial value called the seed (
X(0)) is provided to the algorithm and a number is generated.Each new number (
X(n+1)) is generated by taking the previous number (X(n)) and applying the above formula.The modulo operation ensures that the generated number falls within a specified range i.e. [0,
m-1].
Choosing Parameters In LCG
Commonly used values for the parameters are:
m: A large prime number which is often a power of 2 (e.g., 2³¹ — 1)a: usually chosen to have a full period (e.g., 1664525)c: often a small odd number (e.g., 1013904223)
Implementation in Python
class LCG:
def __init__(self, m, a, c, seed):
self.m = m
self.a = a
self.c = c
self.seed = seed
def random(self):
self.seed = (self.a * self.seed + self.c) % self.m
return self.seed / self.m
# Example usage:
m = 2**31 - 1 # Large prime modulus
a = 1664525 # Multiplier
c = 1013904223 # Increment
seed = 42 # Initial seed value
lcg = LCG(m, a, c, seed)# Generate and print 10 random numbers between 0 and 1
for _ in range(10):
print(lcg.random())
#0.29316619983556036
#0.9409172320463309
#0.7278078648856877
#0.8584347953360689
#0.6498427161247669
#0.9191935234326839
#0.0717277340924962
#0.07872625816554123
#0.2970089434166481
#0.283676542008145Limitations
Although LCG is a fast and lightweight algorithm, it can generate predictable results making it unsuitable for cryptographic purposes.
(Remember that it is not a truly random number-generating algorithm.)
Cryptographically secure random number generators (CSPRNGs) are recommended for such applications.
Also, an important reminder is that you should (almost) never implement your own Cryptographic functions.
If you are launching a production-ready application, always use the standard cryptographic libraries available for your programming language instead of an algorithm from scratch.
These libraries have been rigorously tested over the years and will save you from significant losses in the future.