# How do I prove that this PRNG is easily distinguished from a random sequence of numbers (modulo m)?

I was studying Crypto, and this question came up. Using a PRG like the multiplicative congruence generator:

$b_{i+1} = a \cdot b_i \mod m$

How do I prove that the output of this PRG, or any PRG's whatsoever is easily distinguished from a random sequence of numbers?

• What have you tried? Where did you get stuck? (We expect you to make some effort before asking here.) Do you know what the definition of "distinguishing from a random sequence" is? Have you tried plugging into the definition? Where did this problem arise? What's the context/motivation? Why do you need to prove it? If it's a textbook exercise, have you reviewed the material on PRGs and on elementary number theory? – D.W. Oct 24 '13 at 18:04
• Since this looks like homework, here are a few pointers: Linear congruential generators have certain structures in the "higher dimensions" if you consider sequences of numbers as vectors. This is called the "Marsaglia effect". These structures can be detected by statistical tests, e.g. the spectral test. – tylo Oct 25 '13 at 15:08

Well, this is essentially homework (it wasn't assigned, however you are attempting to learn from it), and so I won't give you an explicit answer; instead, I'll try to point you in a direction where you can figure out the answer yourself.

First of all, how would you solve this if you were given the values $a$ and $m$?

Once you have answered that, let us assume that you were given the output of such a sequence, and also given the value of $m$. How would you recover the value $a$?

Now comes the hard part, let us assume that you were given the output of such a sequence, but did not know either $a$ or $m$; how would you recover the value $m$?

Hint on the last question: let us assume we were given three consecutive values $b_1, b_2, b_3$ with $b_2 = a b_1 \bmod m$, $b_3 = a^2 b_1 \bmod m$; how can we combine the values $b_1, b_2, b_3$ to come up with some value which is a multiple of $m$? (Hint: consider $b_2^2$ and $b_1b_3$)? How can we use that to recover $m$?

Last question: let us assume that the sequence we were given was not generated by such a generator; what happens when we attempt to recover $m$ using the above procedure?

• If you can prove that this generator ( or any PRG is indistinguishable from a truly random distribution, you have proven that P is not equal to NP. Go collect your million dollar prize from the Clay Mathematics Institute. – William Hird Oct 31 '13 at 5:29