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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
5
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)
-
$\begingroup$ Thanks for your answer. Sorry, according to your notation the 51-th term $x_{50} = 2.$ I simulated with $x_0 = 5, a = 3, c = 7, m = 19$ $\endgroup$ – PT272 Jul 8 '16 at 11:46
-
$\begingroup$ Here are the iterates $\{5,3,16,2,46,42,21,40,34,26,31,22,10,41,4,33,9,24,44,8,7,37,30,5,3,16,2,46,42,21,40,34,26,31,22,10,41,4,33,9,24,44,8,7,37,30,5,3,16,2,46,42,21,40,34,26,31,22,10,41,4\}$. As you can see, it satisfies $x_{50} = 2$ (Count starting from zero) and the other requirements - although it has a short cycle too. The method would likely need more data to find more $m's$ to be exact. $\endgroup$ – Moo Jul 8 '16 at 12:06
-
$\begingroup$ @PT272: Of course, a brute-force approach would also work as you can just cycle through cases for $a, c, m $, but the paper I used is based in theory, which was preferable, but likely not an optimal answer. The brute force would not work for much larger values, but certainly will here. $\endgroup$ – Moo Jul 8 '16 at 12:32
-
$\begingroup$ How many terms are needed to uniquely determine $a,b,m.$ Does it depend whether any of the parameters are co-prime? $\endgroup$ – PT272 Jul 8 '16 at 17:02
-
$\begingroup$ Yes, there are many factors regarding co-primes, but also all these LCG have cycles - so all sorts of other requirements can be placed on the result. When you use real sized numbers, we are typically talking huge periods. The paper I pointed to has some references on the math and other considerations. If we had 2-to-3 times the number of samples, that might help uniquely determine it, but there could be other unforeseen issues until you try it. $\endgroup$ – Moo Jul 8 '16 at 19:08
