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?
$\endgroup$1 Answer
$\begingroup$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)
