Behind Intel's New Random-Number Generator • Hacker News Board

Re: Behind Intel's New Random-Number Generator

#41

Post by palish » Fri, Sep 02, 2011, 3:16 AM UTC

tripzilch wrote: post #38

marshray wrote: post #35

Earlier quoted context omitted.

So what you need is a high-quality Pseudorandom Number Generator (PRNG). You do not need a Cryptographically Secure PRNG. This is good, what you need can be implemented significantly more efficiently than the CS version. As you mentioned, it doesn't help your application to be truly nondeterministic. C rand() is about the worst one you can find. Mersenne Twister is great statistically, but it's quite expensive in ter…

I've been reading New Kind Of Science recently, intrigued by some of Wolfram's grandiose claims I ran some tests and it indeed turns out that the Rule 30 cellular automaton is a very high quality PRNG (as long as you pick the right bits). It's a very simple algorithm and very parallel too. It's just that my version picked one bit per generation (the middle one) and the period of the PRNG is determined by the size of…

Whoa, cool. Thanks!

I don't suppose you have the code lying around...? Even if it's not pretty, it would still be a big help! =)

Re: Behind Intel's New Random-Number Generator

#42

Post by palish » Fri, Sep 02, 2011, 3:20 AM UTC

marshray wrote: post #35

palish wrote: post #32

Earlier quoted context omitted.

You'll have to take my word for it, or try it yourself: there are visually noticeable repetitive patterns that are a direct result of the naive PRNG. For example I once modeled raindrops as falling billboards that struck the ground at some random (x,y) in your field of view, followed by a "splash" animation billboard where it struck the ground. I started by using C rand() to determine the random (x,y) of the raindrop…

So what you need is a high-quality Pseudorandom Number Generator (PRNG). You do not need a Cryptographically Secure PRNG. This is good, what you need can be implemented significantly more efficiently than the CS version. As you mentioned, it doesn't help your application to be truly nondeterministic. C rand() is about the worst one you can find. Mersenne Twister is great statistically, but it's quite expensive in ter…

As I understand GPU programming, you want to maximize parallelism. Ideally, you would have something small enough to have an independent generator for each processor. You should be able to generate perfectly random-looking numbers using 64 or 128 bits of state storage and a handful of instructions per 32-bits of output.

A perfect assessment.

It's why I keep learning about every field --- there are so many areas that turn out to be applicable in different domains.

For example, "variance shadow maps" create soft shadows using statistical analysis. (I wish they were practical. It's just an example.)

I'll check out the Skein function, thanks.

Re: Behind Intel's New Random-Number Generator

#43

Post by Daniel_Newby » Sat, Sep 03, 2011, 2:49 AM UTC

ghshephard wrote: post #31

Daniel_Newby wrote: post #21

Earlier quoted context omitted.

Nothing needs gigabit rates of random numbers. Consider a Monte Carlo algorithm on a 2 GHz processor, with a 50 instruction cycle inner loop, using a 64 bit random value per loop: it needs 2.5 Gb/sec of random bits.

Perhaps this should be better written as "Nothing needs gigabit rates of _cryptographically strong_ random numbers." Using a megabit rates of cryptographically strong random numbers to seed a PRNG would be fine for most purposes. Can anyone think of a reason why you would want/use gigabit rates of truly random numbers instead of using a slower rate to see a PRNG?

True. Although the new Intel system is not cryptographically secure.

Gigabit true random numbers could be used to modulate a jam-resistant radar signal. That makes it difficult for an opponent to use active electronics to cloak their target, even in principle. However actual systems would use dedicated hardware, not an Intel chip.

The profoundly paranoid could interleave true random bits with their data bits before encrypting (discard them on receipt). Pattern analysis would become much more difficult.