Generating sequences using the linear congruential generator

Question

I came across the linear congruential generator on Wikipedia:

http://en.wikipedia.org/wiki/Linear_congruential_generator

I gather that for a particular choice of the modulus, multiplier and increment, the generator would generate a unique sequence. However, is there any way to determine the values of modulus, multiplier and increment that I need to create a particular finite sequence?

For instance, if I chose the modulus as 8, the multiplier as 1, and the increment as 5, I obtain the sequence 5, 2, 7, 4, 1, 6, 3, 0, assuming a seed value of 0. Now if I wanted the sequence 2, 11, 5, 9, 6, 22, how do I determine what values of the parameters to choose?

Answer 1

This is not a full solution, but something that may help. Let $a_n, n=1,2,3,\ldots$ be your sequence, and fix a natural number $k$. Then the vector $(a_{k+1},a_{k+2},a_{k+3})$ is a linear combination of the vectors $(a_k,a_{k+1},a_{k+2})$ and $(1,1,1)$ modulo the modulus $=N$, because the same (affine) linear mapping always gives the next entry. Therefore the determinant $$ \left|\begin{array}{lll} 1&a_{k}&a_{k+1}\\ 1&a_{k+1}&a_{k+2}\\ 1&a_{k+2}&a_{k+3} \end{array}\right| $$ must be zero modulo $N$.

As an example let's analyze your first sample sequence. With $k=1$ we get $$ \left|\begin{array}{lll} 1&5&2\\ 1&2&7\\ 1&7&4 \end{array}\right|=-16, $$ so $N$ must be a factor of 16. With $k=2$ we get $$ \left|\begin{array}{lll} 1&2&7\\ 1&7&4\\ 1&4&1 \end{array}\right|=-24, $$ so $N$ must be a factor of 24 as well. Therefore $N \mid 8$, and an inspection of the sequence shows that a proper divisor of 8 is out of the question.

If you can deduce $N$ in this way, then finding the remaining coefficients should be easy using the theory of systems of modular equations.

Answer 2

Not every finite sequence can be obtained by a linear congruence generator. In fact, the one you request cannot.

Note that we must have $m\geq 23$ in order to "get" $22$ as an answer. We have that you are requiring: $$\begin{align*} 2a + c &\equiv 11 \pmod{m}\\ 11a+c &\equiv 5\pmod{m}\\ 5a+c &\equiv 9\pmod{m}\\ 9a+c &\equiv 6\pmod{m}\\ 6a+c&\equiv 22\pmod{m}. \end{align*}$$

Subtracting the first congruence from the second, we get $9a \equiv -6\pmod{m}$; subtracting this from the fourth congruence, we obtain $c\equiv 12\pmod{m}$. So now we know the value of $c$, which gives $$\begin{align*} 2a &\equiv -1\pmod{m}\\ 11a &\equiv -7\pmod{m}\\ 5a &\equiv -3\pmod{m}\\ 9a &\equiv -6\pmod{m}\\ 6a &\equiv 10\pmod{m}. \end{align*}$$ Multiply the first congruence by $3$ to get $6a\equiv -3\pmod{m}$. Since we also need $6a\equiv 10\pmod{m}$, we must have $10\equiv -3\pmod{m}$, or $13\equiv 0\pmod{m}$. But that means that $m=1$ or $m=13$, which contradicts our requirement that $m\geq 23$.

There are other contradictions in this system: multiply the third congruence by $2$ to get $10a\equiv -6\pmod{m}$, and subtracting from the second congruence we get $a\equiv 3\pmod{m}$. But subtracting $9a\equiv -6\pmod{m}$ from $10a\equiv -6\pmod{m}$ would give $a\equiv 0\pmod{m}$, so we would need $3\equiv 0\pmod{m}$, again a problem.

Or note that $2a\equiv -1\pmod{m}$ tells you that $\gcd(2,m)=1$, so that $6a\equiv 10\pmod{m}$ is equivalent to $3a\equiv 5\pmod{m}$, and multiplying by $3$ gives $9a\equiv 15\pmod{m}$; comparing with $9a\equiv -6\pmod{m}$ gives $21\equiv 0\pmod{m}$, so $m$ would have to divide $21$. Etc.