The Blum-Blum-Shub psu-random generator is this: x := x^2 mod M, then output LeastSignifBit(x) where M=p*q, with p<q both primes which both are 3 mod 4. The initial x must be relatively prime to M and not 1. It is "provably random" in the sense that if you wanted to "go backwards in time" to guess the random bit for the timestep 1 before the first bit you'd seen, then that would be impossible for you to do, for any guess correctness chance 0.5+epsilon, unless you did computation at least as hard as factoring M. (Here I am assuming you know M, but do not know p and q.) In other words this psu-random bit generator is immune to every statistical test that does less than Factoring(M) worth of computation. This also works if M is a product of any number (>=2) of distinct primes that are 3 mod 4, but it usually is presumed that M is hardest to factor if it has only 2 prime factors, in which case nobody cares. OK, I now make a very simple, but apparently new, remark. Just iterate y := y^2 mod p and z := z^2 mod q and then LeastSignifBit(x) at any time, equals the XOR of the LeastSignifBits of y and of z at that time. Because: if x were constructed by chinese remaindering y and z, that'd happen. Cool moral: This tells us that just by XORing two bitstreams that by themselves would fail randomness tests, we can make something immune to all efficient tests. So we might now CONJECTURE that if K different psu-random bitstreams are XORred together (all unrelated and with relatively prime periods) then in general there is going to be no statistical test that kills it, that is more efficient than brute force trial of all possibilities for the states of K-1 of the generators, then applying some test which breaks the final generator given that the other K-1 are known. I admit that conjecture is vaguely stated... and maybe too strong... But: here is something concrete. Suppose I give you three circular lists of the first N bits of pi, of e, and of EulerGamma. I then perform a secret circular shift of each of the 3 lists, and then output their XOR: N bits of output. Tell me: could you then detect anything nonrandom about those N bits, in any faster than quadratic(N) expected time? I do not see how... Therefore, I conjecture that if you XOR the outputs of three different psu-random generators of periods P1, P2, P3 and secret initial states, then "unless they were related or crappy" no statistical test will be able to tell the result is nonrandom, unless it does at least P1*P2*P3/max(P1,P2,P3) expected computation. This conjecture will really kick butt re the current world of crypto and PRNGs, if true. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)