SPIN's True Randomness can't be BUSTed
cessnapilot
Posts: 182
Hi,
A new object has been just appeared in OBEX containing a Battery of Useful Stat Tests (BUST). With this object one can test & verify any random number generator. See
http://forums.parallax.com/showthread.php?p=839776
In the object the True Random Number Generator of SPIN_TrigPack is checked. This is written (only) in SPIN and gives you different random sequences after each reboot. If only one can explain that...
Of course, you can test any other RNG with this object. Randomness is all around. You have not to model it, just use it.
Cheers,
Istvan
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Intentionally Left Blank
A new object has been just appeared in OBEX containing a Battery of Useful Stat Tests (BUST). With this object one can test & verify any random number generator. See
http://forums.parallax.com/showthread.php?p=839776
In the object the True Random Number Generator of SPIN_TrigPack is checked. This is written (only) in SPIN and gives you different random sequences after each reboot. If only one can explain that...
Of course, you can test any other RNG with this object. Randomness is all around. You have not to model it, just use it.
Cheers,
Istvan
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Intentionally Left Blank
Comments
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
1. It gives a different sequence after each reboot.
2. Statistical tests verify it. (More or less independently of·any subjectivity)
3. You can't predict it. (Me, too)
4. It has practically the same statistical parameters as one with TrueRandom
Anyway, thank you for the first opinion to that TRNG in SPIN. I really appreciate it.
Cheers
Istvan
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Intentionally Left Blank
This is a true RNG:
www.idquantique.com/true-random-number-generator/products-overview.html
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
Bah Humbug ! My programs do it all the time [noparse]:)[/noparse]
Anyway are we talking about the Spin true random number generator that uses jitter of the PPL to get entropy, which is then not just a computer program?. Or something else?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
but can you reproduce it with a second Prop (the PLL-jitter generator) ? if not... it is random enough [noparse]:)[/noparse]
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Visit some of my articles at Propeller Wiki:
MATH on the propeller propeller.wikispaces.com/MATH
pPropQL: propeller.wikispaces.com/pPropQL
pPropQL020: propeller.wikispaces.com/pPropQL020
OMU for the pPropQL/020 propeller.wikispaces.com/OMU
pPropellerSim - A propeller simulator for ASM development sourceforge.net/projects/ppropellersim
Random enough.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
8x8 color 80 Column NTSC Text Object
Wondering how to set tile colors in the graphics_demo.spin?
Safety Tip: Life is as good as YOU think it is!
Perhaps this thread should be titled "SPIN's True Randomness can't be trusted".
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
Post Edited (Leon) : 7/3/2010 6:11:06 PM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
8x8 color 80 Column NTSC Text Object
Wondering how to set tile colors in the graphics_demo.spin?
Safety Tip: Life is as good as YOU think it is!
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
Post Edited (Leon) : 7/4/2010 2:51:25 AM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
Wether a sequence of numbers is random or not is not a question of taste.
Neither has it any relation to its physical source, being quantum or not. The entropy origin of the numbers does not matter at all.
Neither matters the creating device of the sequence, being a computer or not, or a sorcerer, dice or whatever.
Randomness is a well defined mathematical property of a sequence of numbers. A property that can be investigated, analyzed and tested.
Finicky mathematicians figured out long ago what properties of truly random sequence of numbers has.
They invented test statistics based upon the ideal properties of randomness. Those people were really smart.
A test statistic is used to put a numerical value on the departure from the ideal randomness. Thus the test statistic allows a judgement to be made about how far the actual data is from the theory.
To use the test statistic a level of significance and a critical value must be determined. If the test statistic exceeds the critical value for a given test then the true randomness of the given· sample sequence is rejected.
BUST uses 5% of statistical significance. Thus the probability of observing a test statistic value as or more extreme than the critical value is 0.05 for an ideal generator. In other words, even a perfect generator fails at 5% of the tests.
What we should do with a given tested generator is to run·the tests infinite times and find out the probability of the actual fails. If that deviates from the expected value of the ideal generator, we can conclude that the tested generator is not perfect.
But we do not have infinite time to do that. So, we accept a confidence interval, calculated from the average and standard deviation of the fails, to decide the question with a given confidence.
And the result is not sure again. Such is life.
A quantum effect based generator fails at 5% percent of BUST's tests, too. If not, it is not random, just a fake. Take care to avoid the snake-oil advertising of 'True Randomness'.
Cheers,
Istvan
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Intentionally Left Blank
I agree with you, but then again I don't.
Consider a single "black box", that cannot be stopped, restarted or otherwise tampered with, generating a sequence of numbers by some unknown mechanism. It is impossible to definitively prove the randomness of that sequence. You can apply whatever statistical tests you like to that sequence and you will never conclusively prove it to be random or not. Perhaps it's taking it's entropy from a universe of quantum events but perhaps also it's just printing the tail end of the digits of pie which we have not and cannot get to yet but are not regarded as random.
Cessnapilot: "Neither matters the creating device of the sequence, being a computer or not..."
I have to take issue with that statement as well. By "computer" we generally mean some reliably functioning Turing machine. In this context running a program to generate some sequence. In that case the algorithm is the point. Once the algorithm is defined so is the sequence of numbers it can produce. Therefore the sequence cannot be random.
In the face of all this what do we do?
Well we cook up some statistical tests as you describe. But your description contains words such as "judgement" and "confidence" and concludes "And the result is not sure again".
So it looks to me like a matter of taste as to when I give up trying.
P.S. I love the Dilbert cartoon re:. randomness that you see here www.random.org/analysis/
P.P.S. The Diehard battery of randomness tests was found to fail badly after some years of use. Wish I could find the link to that story.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
www.cs.auckland.ac.nz/CDMTCS/chaitin/sciamer.html
Not everyone agrees with him, of course.
Statistical confidence levels are completely arbitrary. They can be avoided by using Bayesian techniques.
The digits of PI (and any other transcendental number) probably are random:
news.bbc.co.uk/1/hi/sci/tech/2146295.stm
Physics ultimately depends on quantum events being random. Quantum-based RNGs are the best source of randomness we have. They are used extensively in research establishments.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
Post Edited (Leon) : 7/4/2010 12:12:43 PM GMT
Here is where we are entering the world of semantics or even philosophy.
The digits of PI, in my mind, for sure are not random. That is to say there is only one value of PI and every time you calculate it, down to however decimal places you can manage, it will be the same. As you said "Random numbers can't be generated by a computer program." Which is basically saying again that once the algorithm is defined so is the sequence. An algorithm cannot generate random numbers. PI is calculated from algorithms and therefore is not random.
But the there is the looser definition of "random" is at work when people talk about the digits of PI. They are trying to say that there is no pattern, it never repeats etc etc. Basically the thing is we don't know what they are and cannot predict what they are except by calculating PI. To me this is not strictly random, just unknown. Of course there is a pattern to the digits of PI. It's the pattern you get when you perform the calculation of PI !!
As for quantum events. I could argue from your statement that:
a) Everything that ever happens is caused by quantum events.
b) Therefore everything is a good source of randomness.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
Everything ultimately depends on quantum events, but in our macro world, they are irrelevant. Everything isn't a good source of randomness, because something like noise in a resistor, which is sometimes used, depends on things like temperature. External effects like that don't influence events at the quantum level. That is why quantum RNGs are so popular. They aren't expensive, the Quantis unit costs €600, IIRC.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
"A series of numbers is random if the smallest algorithm capable of specifying it to a computer has about the same number of bits of information as the series itself"
Using that definition of "random": Given that we can now calculate PI to billions of digits and I presume the programs that do it are not billions of bytes long then I conclude that PI is not random.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
Anyway, I still maintain that the SPIN program mentioned doesn't generate true random numbers.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
Post Edited (Leon) : 7/4/2010 12:44:38 PM GMT
My view is that thermal noise coming out of a resistor, opamp or other electronic device is a perfectly good source of randomness. As is some mechanical device tossing coins or throwing dice. There are many others.
The problem seems to lie in how susceptible to outside tampering these things are. For example the signal from the thermal noise of your resistor might be swamped by some other electromagnetic interference getting into the system and "fixing" the result.
In this respect radioactive decay, for example, cannot we assume be influenced. 241Am either decays emitting a gamma ray or it does not. and it does it when it feels like it at random.
However that is of no use unless you can be sure that your entropy detector, detecting the decays, is also immune to outside interference and "fixing" or biasing the result.
By the way, quantum events are not always so disorganized, the red light of a helium-neon laser comes from certain energy level transitions of electrons in the gas, that is quantum events. Look how well they synch up and produce a coherent beam of light.
Further, if you were using 241Am decay as a randomness source. A possible way to "fix" the result is to add enough extra Am around it, about 60Kg, such that it goes critical. See how random that is[noparse]:)[/noparse]
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
With a laser, you are actually looking at a macro effect, not something based on the properties of individual photons.
See how idQuantique handles the processing of data from the single-photon detector they use in their Quantis unit.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
True enough and quite reasonable given the desire for immunity from external influence I discussed. I still maintain that you quantum entropy detector has to be built with external influence in mind. Not at the quantum end so much but on the path up from there.
Nothing to say about the "PEAR" people. They just seem to be loony toons to me[noparse]:)[/noparse]
I absolutely disagree that a Laser is a macroscopic effect. That is it is NOT like Newtonian mechanics and utterly depends on quantum mechanical properties of the atoms used. Without introducing the idea of "quanta" of energy the laser cannot be explained. With that comes all the associated quantum mechanics.
Admittedly you need a lot of HeNe in a tube to make a laser, for example, so it looks macroscopic.
I refer you to this history of the laser: www.aps.org/publications/apsnews/200508/history.cfm
In which we read "If one has a large collection of atoms containing a great deal of excess energy, they will be ready to emit a photon randomly. However, if a stray photon of the correct wavelength passes by (or, in the case of a laser, is fired at an atom already in an excited state), its presence will stimulate the atoms to release their photons early–and those photons will travel in the same direction with the identical frequency and phase as the original stray photon."
What I'm kind of getting at is that with random number generators based on quantum decay one has a similar situation to that described above. A large collection of atoms...excess energy... ready to emit...randomly...However....
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
This analogous to a the electrons of a single atom decaying from a high energy level to a lower one. It will happen at random. But surround the thing by enough similarly energized atoms and you get stimulated emission and coherence.
This is a great debate, but it reminds me of a time two decades ago when I was working on a hand held military wireless communications project. When we came to the requirment for randomness and entropy for the crypto we had a problem. It pretty much halted development for a month as all the team members got to grips with "what is randomness", what does "random" mean and where do we get some of this? Didn't help that we had GCHQ looking over our shoulders to make sure we got the right kind[noparse]:)[/noparse]. The discussion got similarly philosophical then.
So we should give this a little rest whilst I get Zog moving[noparse]:)[/noparse]
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
A pritchel is a pointy thing used by blacksmith's to make holes in things like horse shoes, BTW.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM
Post Edited (Leon) : 7/4/2010 3:57:50 PM GMT
I think that what they needed for their purposes was an event of sufficient
randomness that could be shifted by some sort of unknown method(force?).
Crypto quality was not needed. If the stream of data from the PEAR RNGs shifted
in a significant way that was correlated to major events then that's all that was necessary.
I think electrical noise like that produced by a noisy diode was sufficient.
If a poor-quality quantum RNG shifts at the right time then that is good enough and provides the
same level of proof as a perfect quantum RNG would.
Schrodinger's cat is not dead.
Schrodinger's cat is dead.
Schrodinger's cat is not dead.
Schrodinger's cat is dead.
Schrodinger's cat is not dead.
Schrodinger's cat is dead.
Schrodinger's cat is not dead.
Schrodinger's cat is dead.
Schrodinger's cat is not dead.
Schrodinger's cat is dead.
Schrodinger's cat is not dead.
Given the vast number of events that take place each day, a poor quality RNG is more likely to correlate with one of them than a good quality one, I would have thought. The PEAR people have even claimed that they detected anomalies *before* something happened! No one has been able to replicate their results, of course. They couldn't even replicate them themselves in a different lab.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM