Parallel Random Numbers: As Easy as 1, 2, 3 (2011) [pdf] | Hacker News Reader

Parallel Random Numbers: As Easy as 1, 2, 3 (2011) [pdf]

thesalmons.org

18 pointsnkurz7 comments

As I commented on reddit;

I've not read much, but the start where it says

> There are two approaches to parallelizing a PRNG—multistream and substream—but both approaches have practical difficulties for conventional PRNGs.

just screams "use PCG random!" to me. PCG random numbers support good, independent random streams really easily and also support substream partitioning. These don't require any challenging seeding, and they're some of the fastest RNGs out there. They're also small - 64 bits for a 64 bit period, 128 for 128 bit period, etc. Probably double that if you need streams, unless you're using their address for stream splitting.

'Course, there was no option for this in 2011.

Also, I'd be interested to know if the PCG test in Figures 7 and 15 of the paper[1] can be applied to this generator and, if so, how it fares. It's the only test I know of that isn't pass-fail, so helps give extra context on how strong an RNG actually is.

Also, where it's said

> On the other hand, many of the most widely used PRNGs fail quite dramatically, including all of the linear congruential generators

do note that a 92 bit LCG outputting 32 bit integers, and a 128 bit LCG outputting 64 bit integers do in fact pass the statistical tests. LCGs are, in many ways, actually pretty good with larger state sizes. Not that implementers will take note :P.

[1] http://www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.p...

Summarizing, the paper suggests that you can generate high quality pseudorandom numbers by hashing a counter with a cryptographic hash (such as AES). Since AES has hardware support in modern processors, this is fast: less than 2 cycles per byte of randomness. If you do fewer "rounds" of encryption than used for cryptography, you can pass all existing tests for randomness with run time of less than 1 cycle per byte. Using a counter as the state makes it very easy to skip ahead in the sequence, and to distribute "streams" across multiple processors.

I'm sort of surprised this could be a paper published in 2011. Isn't this pretty much the obvious thing to do? Counter hashing is a well known way to generate good random numbers, and it seems almost as obvious how you'd scale to multiple processors.

Yeah, considering what was described is essentially aes-ctr

Forgive my ignorance in cryptography. If a series of pseudorandom numbers can be trivially replicated by figuring out the counter and hash algorithm (seems simple with open source software), how can the psuedorandom numbers be said to be of high quality?

The key(s) used for the cipher would need to be randomly seeded in some way that an attacker could not easily guess (e.g. with a different CSPRNG).

Edit: And for hash functions, you can generate some random bytes that you append the counter to before putting it through the hash algorithm. The same as above, if those bytes are hard to guess then the construction should be safe.

is the 'web' button on HN new?

Reply on news.ycombinator.com