# System of congruential equations

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.

-

## migrated from security.stackexchange.comJul 13 '12 at 9:34

This question came from our site for Information security professionals.

–  Ｊ. Ｍ. Jul 13 '12 at 10:03
It's two linear equations in two unknowns. I'm sure you know how to solve a system of two linear equations in two unknowns. –  Gerry Myerson Jul 13 '12 at 10:47

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).

-