This mini-post breaks down how to solve for the constants of an Linear Congruential Generator (LCG) given:

• known power-of-two modulus (going to use 32-bit)
• three sequential outputs $\left(u_1,~u_2,~u_3\right)$

Recall that LCGs (with implied mod) can be written as:

\begin{align*} u_{i+1} = m~u_i + c \end{align*}

where $m$ and $c$ are (hopefully) well chosen constants. Given our known outputs we have:

\begin{align*} u_{1} = m~u_0 + c \\ u_{2} = m~u_1 + c \\ u_{3} = m~u_2 + c \\ \end{align*}

Let’s solve for $m$. Start by subtracting $u_3$ from $u_2$

\begin{align*} u_2 - u_3 = m \left( u_1 - u_2 \right) \end{align*}

To isolate $m$ we need to move the $\left( u_1 - u_2 \right)$ to the other side which we can do by multiplying both sides by the modulo multiplicative inverse (denoted below by $x^{-1}$):

\begin{align*} m = \left(u_2 - u_3\right)\left( u_1 - u_2 \right)^{-1} \end{align*}

We can now solve for $c$ by (choosing $u_2$ equation):

\begin{align*} c = u_2 - m~u_1 \end{align*}

and while we’re at it for the seed $\left(u_0\right)$

\begin{align*} u_0 = m^{-1}~\left(u_1-c\right) \end{align*}

and “Bob’s your uncle”. Code given below. So the only tricky part in this simplified case is being aware of the mod inverse. This extends to other “bases” by updating the inverse function and performing the mod at each step. If the base is an unkown, then things get a bit more tricky (SEE: How to crack a Linear Congruential Generator)