4

Looking around a bit I have found that most solutions for generating a true random number involves inspecting natural phenomenon.
But is it really necessary?
I mean, assuming that Pi has random infinite sequence of digits as far any system could tell, couldn't we just build an algorithm which will look something like this (assuming 64 bits architecture):

  1. Take the first 64 bits.
  2. Cast the bits into double
  3. Take next 64 bits
  4. Cast the bits into double
  5. etc...

Of course this could be enhanced (involving seeds, casting to Integers and so on...)

Does this sounds right or am I missing something?

Note:
About the assumption about pi, according to Wikipedia it is widely believed that Pi is a Normal number. Shouldn't this be enough? If it can't be disproved, Shouldn't it be enough for any practical system?

Community
  • 1
  • 1
Avi Turner
  • 10,234
  • 7
  • 48
  • 75
  • How many times do you do that step? If you do it a fixed number of times, you will always get the same number. So in deciding how many times to do it, you need a random number generator: you're back at the start. (You certainly couldn't use this series in cryptography: every private key anyone generated would be the same!) – David Robinson Oct 23 '13 at 06:07
  • @DavidRobinson It depends on how many random numbers you need. Eech step generates a random number. No conection to [David Robinson](http://en.wikipedia.org/wiki/David_Robinson_(basketball)) I assume :) – Avi Turner Oct 23 '13 at 06:11
  • http://www.random.org/ Nice site about true random numbers, though I don't think it offers any programming help – Paul Samsotha Oct 23 '13 at 06:12
  • 7
    @AviTurner: But it's always the *same series* of random numbers, which destroys the purpose of an RNG. So let's say I wanted to use an RNG to generate a private key for my encryption. I generate a random number using the digits of pi, and get a key. Someone else generates a random number using the digits of pi, they get their key. Our keys are exactly the same- not a very good encryption. (As for Spurs #50, I think my profile picture leaves little room for doubt) – David Robinson Oct 23 '13 at 06:14
  • @peeskillet: Aren't the numbers generated by random.org chaotic in nature (thus not truly random)? – npinti Oct 23 '13 at 06:15
  • @npinti What do you mean by chaotic? The site says, "The randomness comes from atmospheric noise". I have no idea what that means in terms of randomness – Paul Samsotha Oct 23 '13 at 06:19
  • @DavidRobinson I agree that given identical seeds, you will get Identical series. but couldn't this be solved by inserting a seed based on, let's say, a transform made on your MAC address, of course it is not unique, but any one would agree, you got this MAC address randomly... – Avi Turner Oct 23 '13 at 06:23
  • 2
    @AviTurner: So you do agree that you need to decide how many steps to perform (unless you meant something else by "inserting a seed"). Now you're competing with other pseudorandom number generators such as a Mersenne twister: it takes a seed and it spits out a number pseudorandomly. The question is then whether pi is a good pseudorandom number generator, and it's not, for reasons rici discusses: it's just much slower than other pseudorandom approaches. (And slower often means fewer cycles, which means less secure). – David Robinson Oct 23 '13 at 06:30
  • 2
    Unrelated: MAC address is not a very good seed: if someone discovered your MAC address (by hacking the router, for example), they could discover the seed. Better would be something like the least significant digits of your current computer time. – David Robinson Oct 23 '13 at 06:33
  • @peeskillet: Chaotic systems are usually systems which have a boatload of variables and are susceptible to even the minor change of one of them (thus making them difficult to guess, also if memory serves, is were the term `God does not play dice` comes from. To my knowledge, atmospheric systems are such systems. – npinti Oct 23 '13 at 06:34
  • 1
    Another note: there are 10 trillion known digits of pi. These take up 9TB of hard drive space and took almost a year of running on specialized systems ([see here](http://www.numberworld.org/misc_runs/pi-10t/details.html)), but let's say you could use *all* of them in your RNG. There are 2^64=1.8*10^19 possible 64-bit integers, so the chance of a given integer appearing more than once in the series is < 1/10 million. That means that if you have an integer from the generator, you could find out the seed and predict the next one (and all future/past ones) just by searching for it in the series. – David Robinson Oct 23 '13 at 06:46
  • @DavidRobinson By seed I meant where I would start taking the digits/bits from. The number of steps depends on how many random numbers the user wants. Regarding the hard drive issue, using the [Bailey–Borwein–Plouffe formula](http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula) you can get them at run time without storing them. – Avi Turner Oct 23 '13 at 06:52
  • @DavidRobinson I guess you are right as far as it goes to security systems. and Pi being a known constant is a vulnerability, which will force keeping the algorithm as a secret. Do you see any issues for non security systems? – Avi Turner Oct 23 '13 at 06:58
  • 1
    @AviTurner: As some of the answers below state, it depends on what you mean by true randomness. Here you're really asking if pi offers "true pseudorandomness": randomness depending on a starting seed, which has to itself be generated in some random way. That's still not getting at the kind of randomness for which people turn to natural phenomena such as radioactive decay, which tries to avoid relying on that starting seed at all. – David Robinson Oct 23 '13 at 07:04
  • @DavidRobinson Thank you for all of you input. it was truly enlightening. – Avi Turner Oct 23 '13 at 07:06
  • @AviTurner: I found the discussion interesting and enlightening as well- cheers. – David Robinson Oct 23 '13 at 07:07

3 Answers3

8

No, it's absolutely not possible!

On a deterministic machine, you can compute deterministic sequences. There is no randomness to be found. Even chaotic systems are just deterministic sequences.

You can indeed generate a deterministic sequence which appears to have the same distribution of digits as one would expect from a randomly generated one. But it's still deterministic.

Pi is completely deterministic: If you and I both generate the sequence of digits in Pi, we both get the same numbers.

I believe you are right in saying the distribution of digits seems to be uniform: but this raises the obvious question: where do we start? We need to choose a random place to start in the sequence to make it 'truly random': thus we are back to square one.

In practice we use sources of what seems to be randomness: Linux will look at times between disc accesses, and keystrokes, and the exact time. But with a little work we can predict all of these more and more accurately, or alter them by fixing our environment.

Hardware random number generators use quantum processes which are believed to be truly random. For example, performing a quantum measurement is believed to be a perfectly random process: no 'better' knowledge of the initial state can help predict the output state (as with chaotic systems).

A paper absolutely worth reading on this subject is "On random and hard to describe numbers" by Bennett, it's quite easy to find with a quick Google.

And here's a nice related XKCD :)

This reminds me of an XKCD...

Ross Hemsley
  • 576
  • 5
  • 14
  • Look at the discussion I had with @DavidRobinson about entrance point. I agree that given an input, the same output will be given from the algorithm, but isn't it enough for any practical system? The numbers in a given system will be random. You are arguing that there is no randomness between a collection of series. – Avi Turner Oct 23 '13 at 07:04
  • @AviTurner: In a comment on a different answer you said you weren't interested in practicality! Now you're saying "it's enough for practical purposes?" :-) – David Robinson Oct 23 '13 at 07:05
  • @DavidRobinson You are correct. The discussion is just to interesting! – Avi Turner Oct 23 '13 at 07:07
  • 2
    It's a different question: If you want 'true randomness'. This is not the way to go. If you want a pseudo-random sequence of digits with the correct distribution of digits. You could maybe use Pi. But there are much more efficient to compute sequences of digits out there that do the same thing. Plus, others have said it's not 'constant time per digit', so if you want to start at a random position, you are quite limited: an attacker 'knows' that you started early on in the sequence! - Also, you may have to compute all the way to the seed before you can continue generating? – Ross Hemsley Oct 23 '13 at 07:09
  • Also: say I use my random number to generate a random angle: using digits of Pi might not be such a good idea in this case! :) – Ross Hemsley Oct 23 '13 at 07:12
  • @RossHemsley: you're right up until the last sentence: as Avi noted in comments elsewhere, the [Bailey-Borwein-Plouffe](http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula) can calculate hexadecimal digit n of pi without calculating the first n-1. – David Robinson Oct 23 '13 at 07:12
  • @DavidRobinson Ah that's interesting. And did someone figure out if there's an algorithm that's constant time per digit? – Ross Hemsley Oct 23 '13 at 07:15
  • @RossHemsley: If there were, it would be an awful lot easier than it is to calculate pi out to greater digits. ([Here are](http://www.experimentalmath.info/bbp-codes/bbp-alg.pdf) some very interesting details of the algorithm, and how long it took to calculate later digits) – David Robinson Oct 23 '13 at 07:17
6

Sure. But why go to all that trouble? Computing π is a complicated task, and it is hard to reason about the results. Also, as far as I know there is no algorithm which will produce digits of π in constant time.

On the other hand, pseudo random generators like the Mersenne twister are designed to be fast to compute, are easily seeded, and allow some amount of analysis (in the case of the twister, the cycle length, for example).

However you compute pseudo-random number sequences, you leave yourself open to prediction attacks if the algorithm is known. (That would be particularly easy in the case of mathematical constants like π.) If you're using the random number as part of a security system, the suspicion that the bad guys could predict the sequence would be an obvious vulnerability.

So for such purposes, "natural" phenomena can have their uses.

rici
  • 234,347
  • 28
  • 237
  • 341
  • Actually the question is just out of curiosity, no practical implementation for now... – Avi Turner Oct 23 '13 at 06:27
  • In case your curiosity gets more acute: http://www.experimentalmath.info/bbp-codes/bbp-alg.pdf Note, however, that the algorithm described there is not linear; it slows down as you get further from the decimal point (another reason not to use π as a source of random digits.) – rici Oct 23 '13 at 06:42
1

Isn't Pi a natural phenomenon as well?

sarwar
  • 2,835
  • 1
  • 26
  • 30
  • True, but unlike the suggestion I have seen so far it does not require additional hardware for inspecting. This actually is a really good comment. Do you think than that the algorithm should work? – Avi Turner Oct 23 '13 at 06:16
  • If you could at will subsample any piece of pi the infinite series, then sure. It doesn't seem like the best approach for random numbers though since the known sequence is well, known. See rici's answer. – sarwar Oct 23 '13 at 06:23
  • Although, If I am not looking for it for security reasons, being known is not an issue... – Avi Turner Oct 23 '13 at 06:31
  • Secure or not if someone can guess correctly better than 10% over infinite iterations guessing between 1-10 then either the sequence isn't random, or they're from the future! – sarwar Oct 23 '13 at 06:35