Breaking Linear Congruential Generators

One way to generate pseudorandom generator is the Linear Congruential Generator. The generator is defined by the congruential relation \[ X_{n+1} = (aX_n + c) \pmod m,\] where \(a, c,\) and \(m\) are parameters of the generator and \(X_0\) is called the seed.

Here is one way we could implement this:

1
2
3
4
5
def getRandom():
    x = 1 #seed
    while True:
        x = (a*x + c)%m
        yield x

However, linear congruential generators are not very secure, i.e. their outputs are fairly predictable.

Here are 8 consecutive outputs from a particular LCG:

1
720555190, 133143292, 350469176, 715002068, 822810950, 400865843, 226553034, 200183345

What is the next output from the generator?

×

Problem Loading...

Note Loading...

Set Loading...