Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

migrated from Jul 13 '12 at 9:34

This question came from our site for information security professionals.

A related question at scicomp.SE. – J. M. 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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.