Efficient Prediction of Linear Congruential Pseudorandom Numbers

[Falken_47]

Homework Statement

Hi everyone! I have a homework question given below:

One scheme of pseudorandom number generator is the linear congruential generator where we pick some modulus m, constant a and b and a seed x0, then generate sequence x1, x2, x3, ... according to the equation:

x(t+1) = mod (ax(t) + b, m)

given that we know m to be 2^31 -1 (a prime number) and we also know the values of x0, x1, x2, x3 and x4, describe how efficiently you can predict x5 up to x9

Homework Equations

x(t+1) = mod (ax(t) + b, m)

x(t+1) = ax(t) + b (mod m)

The Attempt at a Solution

for starter, i plug in the values of x0, x1 and x2 into the equation to form 2 equation:
x1 = ax0 + b (mod m)
x2 = ax1 + b (mod m)

substracting the equations above we get:
(x1 - x2) = a(x0 - x1) mod m

therefore a mod m = (x1 - x2)/(x0 - x1)
after that simply plug in the value of a into equation 1 and we get
b mod m = x1 - (x1 - x2)x0/(x0 - x1)
then since we know the value of a and b we can simply calculate x5 to x9.

My question is whether the method that I'm using is correct, since by using the above method means that given value of m, x3 and x4 are not used at all

 

[Nino MMP]

, so I'm not sure if this is the most efficient way to solve the problem.Any advice will be greatly appreciated, thank you!