Skeptics Guide to the Universe Forums

General Discussions => Tech Talk => Topic started by: Bill K on June 23, 2018, 03:42:35 PM

Title: Random Number Generators: Really Random?
Post by: Bill K on June 23, 2018, 03:42:35 PM
 Hi, guys. It's been awhile since I've been here (although I read the political topics her a lot). Anyway, I play games and obvious random number generators play a massive role. What I am wondering, after talking to a friend studying computer science, if it is possible to create something truly random? I am having a hard time rapping my head around the concept.

 Sincerely, Bill. ʕ•́ᴥ•̀ʔっ
Title: Random Number Generators: Really Random?
Post by: CarbShark on June 23, 2018, 04:38:39 PM
Yes.

The way this is proven is the RNG creates sets of millions of numbers millions of times. Then the results are analyzed to determine if any number has a higher (or lower) probability of being generated than any other number.




Sent from my iPhone using Tapatalk
Title: Re: Random Number Generators: Really Random?
Post by: Alex Simmons on June 23, 2018, 05:53:42 PM
True randomness requires use of naturally random phenomenon (e.g. atomic quantum fluctuations) as input. It's not possible algorithmically to create true randomness without including such natural phenomenon as part of the generation process. It's possible for an algorithm to create sequence of numbers that demonstrate statistical appearance of randomness, however if you know the starting state the sequence can be repeated exactly.
Title: Re: Random Number Generators: Really Random?
Post by: Bill K on June 23, 2018, 07:24:30 PM
True randomness requires use of naturally random phenomenon (e.g. atomic quantum fluctuations) as input. It's not possible algorithmically to create true randomness without including such natural phenomenon as part of the generation process. It's possible for an algorithm to create sequence of numbers that demonstrate statistical appearance of randomness, however if you know the starting state the sequence can be repeated exactly.

Thank you. That is what I thought, but my friend who specializes in computer science (somewhat as you're talking about) believes true randomness can be created in the way you say it cannot.
Title: Re: Random Number Generators: Really Random?
Post by: The Latinist on June 23, 2018, 08:30:59 PM
Most computer scientists will call such algorithms ‘pseudorandom number generators’ instead, recognizing that algorithms run on deterministic machines cannot produce truly random numbers. There are lots of techniques for creating pseudo-random numbers and some of them can give good approximations of randomness; but every one of them will, given enough time, begin to repeat the exact same sequence of random numbers.  For SHA1, for instance, that repetition starts after 2^160 random numbers are generated.  This is why, as others said above, when security is on the line we use true random number generators which draw on system information (temperature sensors, etc) as sources of entropy.
Title: Re: Random Number Generators: Really Random?
Post by: jt512 on June 23, 2018, 08:31:29 PM
True randomness requires use of naturally random phenomenon (e.g. atomic quantum fluctuations) as input. It's not possible algorithmically to create true randomness without including such natural phenomenon as part of the generation process. It's possible for an algorithm to create sequence of numbers that demonstrate statistical appearance of randomness, however if you know the starting state the sequence can be repeated exactly.

Thank you. That is what I thought, but my friend who specializes in computer science (somewhat as you're talking about) believes true randomness can be created in the way you say it cannot.

I think your friend needs to think more deeply about what "true randomness" is.  Computer random number generators, more properly termed "pseudo-random number generators (PRNGs)," are deterministic: given a starting number, or seed, they generate a series of numbers using an algorithm.  Although the sequence of numbers is not "truly random," the algorithms are designed such that the generated sequence cannot be distinguished from a truly random sequence based on a standard set of statistical tests.  Nevertheless, given sufficient time and computing power, it is theoretically possible to analyze the generated sequence and make statistical predictions of future numbers—if the sequence were truly random, this would be impossible even in theory.  But the best PRNG algorithms are so complex that sufficient time and computing power doesn't exist to successfully perform such an analysis.  Hence, for practical purposes, the sequence is as good a truly random sequence.
Title: Re: Random Number Generators: Really Random?
Post by: arthwollipot on June 23, 2018, 09:00:07 PM
The online tabletop gaming platform Roll20.net uses what it refers to as a "true random" source of entropy based on the fluctuations in the power of a beam of light to drive its dice rolling engine, which it calls "QuantumRoll (https://wiki.roll20.net/QuantumRoll)".
Title: Re: Random Number Generators: Really Random?
Post by: Mr. Beagle on June 24, 2018, 09:59:22 AM
To a true determinist, aren't even atomic fluctuations deterministic? More a philosophical question than a practical one.

When I taught intro programming long ago, my final project would often be to have a student programming contest of pseudo-random number generators, tested against some standard criteria fro randomness. The math students tended to outshine the business students here, though.

Title: Re: Random Number Generators: Really Random?
Post by: Noisy Rhysling on June 24, 2018, 11:20:12 AM
Most computer scientists will call such algorithms ‘pseudorandom number generators’ instead, recognizing that algorithms run on deterministic machines cannot produce truly random numbers. There are lots of techniques for creating pseudo-random numbers and some of them can give good approximations of randomness; but every one of them will, given enough time, begin to repeat the exact same sequence of random numbers.  For SHA1, for instance, that repetition starts after 2^160 random numbers are generated.  This is why, as others said above, when security is on the line we use true random number generators which draw on system information (temperature sensors, etc) as sources of entropy.
That's the term I was taught back in the computing neolithic. (Pre-Y2K.)
Title: Re: Random Number Generators: Really Random?
Post by: CarbShark on June 24, 2018, 11:44:19 AM
I believe that Apple’s RNG uses the last digit of a series of time fractions to generate the seed.


Sent from my iPhone using Tapatalk
Title: Re: Random Number Generators: Really Random?
Post by: Noisy Rhysling on June 24, 2018, 12:06:57 PM
The one Clancy used in Clear and Present Danger sounded like it was a good one, but then Clancy was selling it.
Title: Re: Random Number Generators: Really Random?
Post by: Soldier of FORTRAN on June 24, 2018, 12:12:51 PM
my friend who specializes in computer science (somewhat as you're talking about) believes true randomness can be created in the way you say it cannot.

What's his argument?
Title: Re: Random Number Generators: Really Random?
Post by: jt512 on June 24, 2018, 03:43:31 PM
To a true determinist, aren't even atomic fluctuations deterministic? More a philosophical question than a practical one.


Atoms don't care if you are a true determinist.
Title: Re: Random Number Generators: Really Random?
Post by: brilligtove on June 24, 2018, 09:10:18 PM
I can't remember which corp used lava lamps to generate random numbers, but I think I heard about it on Security Now.

Looking...

Security Now Episode 299 (https://www.grc.com/sn/sn-299.htm)

Quote
Steve: Where we'll set up the problem and get into it, but stop short of going into the solutions which have been devised, which are really interesting. I mean, I think - I'm sure I've spoken on the podcast, for example, that somewhere at Sun Computer there was at one time cameras looking at lava lamps.

Leo: Yes.

Steve: Because lava, the flow of the wax in a lava lamp is a chaotic, unpredictable process. And so they were literally digitizing lava lamp images as a source of chaos to feed into their need for random numbers. So anyway, we've got a great podcast this week - lots of interesting updates and news, and the first half of the issue of random numbers in cryptography and the need for them and the problems of, like, that we have of generating them.

I'm not sure it this counts as "pure" randomness. It's chaotic - like a double pendulum (https://en.wikipedia.org/wiki/Double_pendulum) - but not random like the static we used to pick up on the TV, or quantum decay times for a single particle. In practice, sure - utterly unpredictable.
Title: Re: Random Number Generators: Really Random?
Post by: CarbShark on June 24, 2018, 09:27:47 PM
How are we defining “true” random and how do we test it to determine if the output is truly random?


Sent from my iPhone using Tapatalk
Title: Re: Random Number Generators: Really Random?
Post by: arthwollipot on June 24, 2018, 11:26:50 PM
One rule-of-thumb definition that I've heard is that a sequence is random if it cannot be described by any algorithm shorter than the sequence itself.

Not that that helps with your question much but I thought it was interesting.
Title: Re: Random Number Generators: Really Random?
Post by: werecow on July 09, 2018, 07:10:54 PM
One rule-of-thumb definition that I've heard is that a sequence is random if it cannot be described by any algorithm shorter than the sequence itself.

Not that that helps with your question much but I thought it was interesting.

Yup, that one comes from information theory... Specifically Kolmogorov complexity (https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness).

As for the OT, I think true randomness would require something fundamentally unpredictable. Some quantum thing, no doubt. But you can get close enough for basically any practical purpose with more conventional methods.
Title: Re: Random Number Generators: Really Random?
Post by: stands2reason on May 29, 2019, 07:31:50 PM
As noted, RNGs are pseudorandom. The default is that it is typically seeded with epoch time by default.

On POSIX (Linux and others), there is a virtual file /dev/random that will return environmental noise from device drives (e.g. microphone, radios, input devices). It only produces a certain, small amount of noise, but can be used to seed an RNG, if you want to use something other than the time when the program started.

One rule-of-thumb definition that I've heard is that a sequence is random if it cannot be described by any algorithm shorter than the sequence itself.

Not that that helps with your question much but I thought it was interesting.

Most data streams have redundancy, and can be compressed. An actually random or sufficiently pseudorandom source should generate data that appears to be complete noise to a compression algorithm, devoid of pattern. There will be some pattern by chance, but for most blocks of data, the compression algorithm will output a frame with a header indicating that it couldn't actually save space by compression, and then the raw data itself. If you run any compression algorithm on a sufficiently large stream of random binary data (not some representation that doesn't use all byte values in the binary representation), the compression ratio should generally be just over 100%.
Title: Re: Random Number Generators: Really Random?
Post by: John Albert on May 31, 2019, 06:34:23 PM
On POSIX (Linux and others), there is a virtual file /dev/random that will return environmental noise from device drives (e.g. microphone, radios, input devices). It only produces a certain, small amount of noise, but can be used to seed an RNG, if you want to use something other than the time when the program started.

Some processors also utilize minute fluctuations in the core temperatures for this purpose. 
Title: Re: Random Number Generators: Really Random?
Post by: daniel1948 on May 31, 2019, 07:31:38 PM
Pseudo-random number generators are not truly random, but they are plenty good enough for most applications. I used to use the time when the user hit a key to seed the PRNG for card and dice games.