THE GARDEN

Linear Congruential Generator (State and Parameter Recovery)

Updated 19 Sep 2026

• •

  What it is

  • •

    An LCG updates one integer with an affine recurrence. Three consecutive full states usually reveal both unknown parameters when the modulus is known.

• •

  When to apply

  • •

    Use when outputs expose full consecutive states, directly or through reversible digit encoding. Truncated outputs require additional techniques.

• •

  Symbols and assumptions

  • •

    $x_{i+1}=ax_i+c\pmod m$. Known: modulus m and consecutive states $x_0,x_1,x_2$. Unknown: multiplier a and increment c.

• •

  Math — step by step

  • •
    1. Subtract $x_1=ax_0+c$ from $x_2=ax_1+c$. The increment cancels: $x_2-x_1\equiv a(x_1-x_0)\pmod m$.
  • •
    2. Let $d_1=x_1-x_0$ and $d_2=x_2-x_1$. If $\gcd(d_1,m)=1$, multiply by its modular inverse: $a\equiv d_2d_1^{-1}\pmod m$. For prime m, this condition is simply $d_1\ne0\pmod m$.
  • •
    3. Substitute into the first transition: $c\equiv x_1-ax_0\pmod m$. Now compute each future state with the recurrence.
  • •
    4. Verify against an unused fourth state. The first three fit by construction, so rechecking only those three is weaker evidence. If d1 is not invertible, solve the linear congruence with its gcd conditions and gather more states to distinguish candidates.
• •

  Worked example

  • •

    Let m=97 and observe $x_0=7,x_1=38,x_2=96$. Differences: $d_1=31$, $d_2=58$. Since $31\cdot72=2232=23\cdot97+1$, the inverse of 31 is 72.

  • •

    Compute $a=58\cdot72\bmod97=4176\bmod97=5$, then $c=38-5\cdot7=3$. Predict $x_3=5\cdot96+3=483\equiv95\pmod{97}$.

  • •

    Python check: a = (96-38)*pow(38-7, -1, 97)%97; c = (38-a*7)%97; assert (a*96+c)%97 == 95.

• •

  Checks and pitfalls

  • •

    The pasted Lo-Hi service uses m=2^61−1. Recover complete base-52 states before applying the formula; a missing or extra card corrupts every parameter.

  • •

    Predicting ranks does not avoid equal-rank losses: the service treats ties as losses regardless of the higher/lower answer. Track funds as well as RNG synchronization.

• •

  Related

  • •

    Recovering PRNG Outputs from Base-N Digits

  • •

    Extended Euclidean Algorithm

• •

  Python

  • •

    def recover_lcg(x0, x1, x2, modulus):
        a = (x2 - x1) * pow(x1 - x0, -1, modulus) % modulus
        c = (x1 - a*x0) % modulus
        return a, c
    
    a, c = recover_lcg(7, 38, 96, 97)
    assert (a, c, (a*96+c) % 97) == (5, 3, 95)
    

◌ Explore connections in Graph view