Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
As the Rolling Stones say, "You can't always get what you want." You can get the first four values with multiplier 13, increment 26, modulo 41, but then should have 20, 40. –  Ross Millikan Jun 7 '11 at 20:49
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Thank you for the reply :) Are such contradictions present in every modular arithmetic-based generator? Is there a generator that can generate any sequence? –  susmits Jun 7 '11 at 21:09
1  
@susmits: Surely there are no contradictions, if the sequence was generated by a legit linear congruential generator:-).--- You can probably get any sequence you want by using a generator with a higher recurrence depth (a new entry is gotten by a linear combination of two or more previous entries plus a constant). To get some conditions for those, take a look at my answer below. You need to study longer segments/larger determinants (2+recurrence depth). –  Jyrki Lahtonen Jun 7 '11 at 21:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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