* Marc LeBrun <mlb@well.com> [Feb 02. 2012 07:23]:
[...]
Here is my two nano cents: Use a LFSR (over GF(2)) with some polynomial allowing easy mod operation, e.g., one from http://www.jjj.de/mathdata/all-lowblock-irredpoly-short.txt it should span a few words (I consider period 2^128 (Salmon et. al. paper) a bit small, so go for, say >=4 words to get >=2^256 ). [may check Brent's XOR-shift method as well] Together with this one run a (or a few) FCSR (essentially 2^n mod a prime with primitive root 2), XOR some parts of both to get the random numbers. Rate should be reasonably near to how fast you can copy memory (so I'd expect to generate, say, 1 GB/sec on one core; possibly we need to allow for (rather small) buffers). Jumping to any point in the period is trivial once we know the orders of all parts (shift registers). And so we can run instances on as many cores as we like. Here I did _not_ care about "cryptographical security". [I'd speculate that running two (large) LSFR, and one small LFSR whose bits select between the two large one's outputs could do the trick (by causing a huge and hard to determine period). Could replace small LFSR by some other method to avoid ease of analysis (wrt. periods).] If reproducibility is not required (and the user is really paranoid about randomness) XORing the above with some (even weak) source of entropy should make the output pass all tests in existence. Btw. I found the following paper surprising: Paul Leopardi: {Testing the tests: using random number generators to improve empirical tests}, Eighth International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC 2008) proceedings, (2009). URL: \url{http://wwwmaths.anu.edu.au/~leopardi/Leopardi-TestU01-paper-final.pdf}. ...web site down at the moment, can supply final version on request. Note I did never really work on random number generation.