1

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?

J. M. ain't a mathematician
  • 75,051
PT272
  • 309

1 Answers1

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)
Moo
  • 11,311
  • 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$ – PT272 Jul 08 '16 at 11:46
  • 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. – Moo Jul 08 '16 at 12:06
  • @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. – Moo Jul 08 '16 at 12:32
  • How many terms are needed to uniquely determine $a,b,m.$ Does it depend whether any of the parameters are co-prime? – PT272 Jul 08 '16 at 17:02
  • 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. – Moo Jul 08 '16 at 19:08