1
$\begingroup$

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
$\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)
$\endgroup$
5
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.