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?

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Oct 24, 2013 at 18:04
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Oct 25, 2013 at 15:08

1 Answer 1


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?

  • 1
    $\begingroup$ 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. $\endgroup$ Oct 31, 2013 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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