Calculation for linear congruential generator: Setting up equations

Question

Given a linear congruential random number generator $x_{n+1} = (a \cdot x_n + c) \bmod m.$ We are given the first three values $x_0 = 5, x_1 = 3,x_2 = 16$ and the 50-th values $x_{50} = 2,$ what can we say about a,c and m? How to set up the equations to determine those parameters? Are those four values enough for that purpose?

Answer 1

Using How to crack a Linear Congruential Generator, we can possibly crack it with the information given.

We setup the following matrix using the four given values:

$$A = \begin{pmatrix} 5 & 3 & 1 \\ 3 & 16 & 1 \\ 16 & 2 & 1 \\ \end{pmatrix}$$

The determinant of $A$ yields $-141$, which has a prime factorization of $-141 = -1^1 \times 3^1 \times 47^1$.

From this, lets assume $m = 47$ since we know the modulus has to be greater than $16$ from the given sequence.

Now, we can setup the system of congruence's:

$$5 a + c \equiv 3 \pmod {47} \\ 3 a + c\equiv 16 \pmod {47}$$

Subtracting the second from the first (to eliminate $c$), yields:

$$2a \equiv -13 \pmod{47} \implies a = 17$$

We can now substitute $a$ and $m$ into either equation and yield:

$$3(17) + c \equiv 16 \pmod {47} \implies c = 12$$

Finally, we have:

$$x_{n+1} = a x_n + c \pmod m = 17 x_n + 12 \pmod {47}$$

Testing this for $x_0 = 5$ (the first term), yields

• $x_1 = 3$
• $x_2 = 16$
• $\ldots$
• $x_{49} = 2$ (the $50^{th}$ term)