System of congruential equations

Question

I read this question about breaking a LCG, but I can't understand how to solve the system of 2 equations given 3 sequential outputs.

The system should be

X2 = (X1 * a + b) mod p
X3 = (X2 * a + b) mod p

How is it possible to find a and b?

I am assuming that X1, X2, X3 and p are known.

Answer 1

From 'mod', I assume here '=' implies '≡'

Subtracting we get, X2-X3≡a*(X1-X2) (mod p)

If p|(X1-X2), p|b =>p|(X2-2X3)

Else, we can always find an integer c such that c(X1-X2)≡1(mod p) i.e., a modular inverse of (X1-X2) as (p, X1-X2)=1.

Then a≡c(X2-X3)(mod p)

Putting the value of a in one of the given congruence equation, we can get b(mod p).