Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How Do Computers Generate Random Numbers?

digitalbunker.dev

Post reply on HN
Print view View original

21–30 of 52 posts

Re: How Do Computers Generate Random Numbers?

#21

Post by DanBC »

shadowprofile77 wrote: post #5

Just out of layman's curiosity, what would be the problem or difficulty of somehow connecting a more compact type of radio telescope that detects some level of cosmic background radiation and hooking that up to a computer. Would this not be a guaranteed way of generating truly random numbers for any need flawlessly? I know that serious radio telescopes cost way more than any random person could afford to pay but I've…

The problems with that approach come from trying to de-skew the data, and then from sampling the data into whatever port you're using.

Here's a document from 1997 that looks at some hardware RNGs and how they fail: http://www.robertnz.net/true_rng.html

Re: How Do Computers Generate Random Numbers?

#22

Post by DanBC »

Animats wrote: post #10
shadowprofile77 wrote: post #5

Just out of layman's curiosity, what would be the problem or difficulty of somehow connecting a more compact type of radio telescope that detects some level of cosmic background radiation and hooking that up to a computer. Would this not be a guaranteed way of generating truly random numbers for any need flawlessly? I know that serious radio telescopes cost way more than any random person could afford to pay but I've…

A small radiation source works well, although the data rate is low.[1] The idea is to count the number of events (beta particles here) per time interval. Do this twice. If count A > count B, output a 1. If count A Don't use the low-order bit of the count. That has a bias. [1] https://www.fourmilab.ch/hotbits/

The Von Neumann extractor is interesting.

> Von Neumann’s originally proposes the following technique for getting an unbiased result from a biased coin :

> > If independence of successive tosses is assumed, we can reconstruct a 50-50 chance out of even a badly biased coin by tossing twice. If we get heads-heads or tails-tails, we reject the tosses and try again. If we get heads-tails (or tails-heads), we accept the result as heads (or tails).

Re: How Do Computers Generate Random Numbers?

#23

Post by cm2187 »

Is a hardware random number generator that would use environment or electrical sensors to generate noise expensive or hard to manufacture? I would assume this should be part of any standard motherboard given the importance of cryptography. Or does it create an attack vector?

Re: How Do Computers Generate Random Numbers?

#24

Post by Joker_vD »

cm2187 wrote: post #23

Is a hardware random number generator that would use environment or electrical sensors to generate noise expensive or hard to manufacture? I would assume this should be part of any standard motherboard given the importance of cryptography. Or does it create an attack vector?

Why, of course, it's been there for almost 8 years already in Intel processors: https://en.wikipedia.org/wiki/RDRAND

Re: How Do Computers Generate Random Numbers?

#25

Post by jlgaddis »

cm2187 wrote: post #23

Is a hardware random number generator that would use environment or electrical sensors to generate noise expensive or hard to manufacture? I would assume this should be part of any standard motherboard given the importance of cryptography. Or does it create an attack vector?

There was an RNG on the i810 chipset ~20 years or so ago and several VIA chips had onboard RNGs as well.

Modern chips ranging from the one in the Raspberry Pi to Intel CPUs have them too.

Re: How Do Computers Generate Random Numbers?

#26

Post by nestorD »

rurban wrote: post #6

The Mersenne-Twister approach should certainly not be studied anymore, even if some popular old libraries still use it. It fell long out of favor, is too slow, and not good enough. Modern PRNG's can be tested with Dieharder, TestU01 or STS and benchmarked. This article only talks about primitive old LCG's (not any good one) or MT.

Note, however, that it has an extremely large period which is a need for some specific applications (but I do agree that, for most use cases, it should be avoided).

Re: How Do Computers Generate Random Numbers?

#28

Post by benibela »

Straw wrote: post #18
aryamansharda wrote: post #8

Earlier quoted context omitted.

When you say Mersenne-Twister isn't good enough, what are the other shortcomings apart from speed? It seems that even modern versions of Python are continuing to use it...

Its slow, large, and statistically worse than modern PRNGs- and jumping ahead takes longer and a more complicated algorithm. Even a truncated 128-bit LCG has far better properties. See https://www.pcg-random.org/index.html The homepage might come across as a a little overzealous (for example ChaCha quality listed as good rather than excellent), but generally has good points.

However, this page claims PCG is rather bad: http://pcg.di.unimi.it/pcg.php

They recommend to use their xoshiro PRNG.

Re: How Do Computers Generate Random Numbers?

#29

Post by Straw »

benibela wrote: post #28
Straw wrote: post #18

Earlier quoted context omitted.

Its slow, large, and statistically worse than modern PRNGs- and jumping ahead takes longer and a more complicated algorithm. Even a truncated 128-bit LCG has far better properties. See https://www.pcg-random.org/index.html The homepage might come across as a a little overzealous (for example ChaCha quality listed as good rather than excellent), but generally has good points.

However, this page claims PCG is rather bad: http://pcg.di.unimi.it/pcg.php They recommend to use their xoshiro PRNG.

That author has a history of extreme bias and almost-vindictive personal attacks on the author of PCG. See the reddit comments:

https://www.reddit.com/r/programming/comments/8jbkgy/the_wra...

And the PCG author's response: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html

For example, for one of his arguments, he specifically chose a generator called pcg32_once_insecure, which the PCG author does not recommend due to its invertible output function!

Personally, I have read both arguments in detail and I would always use PCG or even a truncated LCG over xoshiro, which has a large size in comparison, potentially worse statistical properties, and no gain- faster in some benchmarks and slower in others.

Re: How Do Computers Generate Random Numbers?

#30

Post by bregma »

IIAOPSW wrote: post #4

My personal favorite RNG is the logistical map. x_{n+1} = 4x_n(1-x_n). There is no hidden seed beyond the current output. Thus if you have a scientific calculator that lets you refer to the value on screen then you can rig it into an RNG. Seeing a simple, non-programmable machine "misbehave" and act random melts my mind a little.

That's still just a linear congruential PRNG with state sizeof(unsigned int). LCG is simple and has well-known flaws.
Post reply on HN