# Proving uniform output of CSPRNG

I have a question concerning the paper by Blum, Blum, and Shub introducing the $$x^2 \mod N$$ Generator. It is clear that the outputs of the generator pass statistical tests for randomness: the larger the $$N$$ value the more uniform the output looks with more iteration. But it is unclear to me how the authors proved the output of the generator is uniformly random. That is, it is not obvious to me that proving difficulty of, say, determining previous states given a present state implies the output of the generator is uniformly random.

Would anyone be able to walk me through a sketch of the proof showing the output of the generator is uniformly random, and thus that the generator is provably secure?

• The output isn't uniformly random. It is merely computationally indistinguishable from a uniform random distribution. (Under specific hardness assumptions and only in an asymptotic sense.) – Maeher Mar 31 at 21:26
• @Maeher I see, then how would you prove it is computationally indistinguishable from a uniform random distribution? – GEG Mar 31 at 22:00

If the primes $$p$$ and $$q$$ are:
then to distinguish non uniformity one basically has to factor $$N=pq.$$ However, as stated by @Maeher in the comments this holds only asymptotically.