Slashdot Mirror
DIY Random Number Generator
Compu486 writes "The guys over at Inventgeek have come up with a project and how artical on building
a random number
generator that is less than 100.00 utilizing radioactive decay. Using some
Linux based open source apps and with a little ingenuity and some parts you probably
have laying around your house you can build your own."
I think it should read:
and how to article on...
And I have to wonder...that is less than 100.00 what?
I know the English may not be the submitter's first language, but it would be nice if the editors....um, you know....*edited* the piece so it made sense.
Michael (Who now sits back and waits for people to pounce on my spelling/grammatical mistakes)
I once collected loads of old broken smoke detectors and ripped out the small cell of americium from each of them.
I placed them into a big ball wrapped in tinfoil (shiney side in), then used my fathers' geiger counter to supply random numbers.
Its been working well, I've been counting the number of years its been running on my fingers, so far I've got to 13.
*note, this is totally false, but there was some stupid kid who did something similar.
liqbase
Whatever happened to just mashing your fists on the keyboard?
If you don't know where you are going, you will wind up somewhere else.
This project seems to work well... http://www.lavarnd.org/
I am a free slashdotter. I will not be modded, blogged, DRM'd, patented, podcasted or RFID'd. My life is my own.
>>
One of the applications I have envisioned for this project is a cheap and easy genuine random number generator. True random numbers in computing are nearly impossible, and successful solutions are very expensive systems based on radioactive decay or atmospheric measurements, for example. Using a small / relatively safe radioactive source and a high res CCD or CMOS sensor and assigning a value to each pixel and perhaps mixing in an algorithm or two with an inexpensive practical PCI card that is capable of generating genuine random numbers. Applications that could greatly benefit from this would be encryption, security applications, Computer AI and the Gambling establishment to name a few.
>>
Actually, no, none of these really benefit from "truly random numbers". The applicability of randomness to AI is... spurious at best? For gambling, you just have to be reasonably sure that someone can't predict in advance what your random sequence is going to be, and the Mersenne Twister plus any unknown piece of data as a seed is good enough at resisting everything our current understanding of mathematics can throw at it. (Yes, thats security through obscurity... in the same way that hiding your server behind locked doors, a firewall, and a secure password is security through obscurity. Its both necessary and sufficient.)
Encryption, similarly, would not benefit from transitioning from an "almost perfect" pseudo-random generator to a "perfect" random generator. For your security to fall based on random numbers, someone needs to be able to not just come up with a theoretical imperfection (ahah, 200 million runs of this random number generator and you'll notice it slightly skews away from these five integers!) but have to crack it wide open. Yay, yawn.
Now, radiation + poorly understood mathematics = geek high, I know. But in terms of practical application this gets a near zero.
Help poke pirates in the eyepatch, arr.
P.S. Clarification: if you're using the Mersenne Twister in a *real life* application that plus a seed value is good enough for a gambling application. For example, if you're generating nice big integers and then taking %6 to get the value of a die or using them to shuffle one or ten or a hundred decks of cards. If, on the other hand, you have some contrived game where you are passing the output directly to the player and continue in the same sequence for a rather improbably long time a player could figure out what sequence the Twister was on and then successfully predict all numbers in advance. But this is one of those earn-you-bonus-points-with-your-CS-professor-and-n ever-use-again pieces of trivia, because in the real world you have to basically design the system to fail for it to fail in this manner.
Help poke pirates in the eyepatch, arr.
Less than 100.00! I've waited at least the past 8 for something like this!
There was a study done that asked a group of people to come up with a string of random ones and zeros. Unsurprisingly, after statistical analysis, they weren't very good. But the fantastic bit was to ask another group to pair off and for each of them to try to outguess the other: let your opponent see your string of ones and zeros so far and then try to make the next bit the opposite to the one they are likely to pick. Amazingly, these random strings were impressively more random. Perhaps we've evolved special pseudo-random number generators to allow us to be sneaky.
[I know, a reference would have been nice, but age does terrible things to your internal bibtex database]
I put together a simple random number generator in the late '90s using avalanche noise from the reverse break-down of a cheap transistor's emitter/base junction. I amplified it with a simple supply noise insensitive 4-transistor amplifier, and pushed it through an 8-bit 40 megabit/sec Analog Devices A/D converter. I xor-ed 80 samples together, while rotating bits in between samples. I used a $3 Lattice PLD to interface the board to an old PCs ISA bus.
... .5*2^i*d^i = .5*(2*d)^i
.5*(2*d)^i
I generated a CD full of random data, which anyone is willing to have if they want it. I've tested it against the "Die Hard" tests, and almost all the 10-meg files pass. There is one test that failed now and then, so I contacted the statistics professor who wrote it. I showed him that his own random number generator, thought to be nearly foolproof, failed the same test with the same probability. It seems I found a bug in his program!
Total cost for components is $10. Anyone who is interested can have schematics for free. Contact me at bill@billrocks.org.
The theory behind it is simple... who cares if the bits from the source are completely random? It turns out you just need a LITTLE true randomness from the source. By xoring bits together that have some randomness, you quickly approach truly random. By my estimate, only God would ever know the difference for the data I generated from perfectly random data, since the board could generate data for billions of years before accumulating even one bit of non-random data in it's output.
Mathematical proof:
Two semi-random bits b1 and b2 each contain small amounts of
non-random noise which we can call d1 and d2. Note that d1 and d2 can
be correlated, and usually are. The notation P(expression) means the
probability that the expression will be 1.
I define P(b1) and P(b2) as:
P(b1) = 0.5 + d1
P(b2) = 0.5 + d2
Both d1 and d2 have a range of -0.5 to 0.5. Xoring b1 and b2 together gives:
P(b1 ^ b2) = P(b1 & !b2) + P(!b1 & b2) = P(b1)*P(!b2) + P(!b1)*P(b2)
= (0.5 + d1)*(0.5 - d2) + (0.5 - d1)*(0.5 + d2)
= 0.25 - 0.5*d2 + 0.5*d1 - d1*d2 + 0.25 + 0.5*d2 - 0.5*d1 - d1*d2
= 0.5 - 2*d1*d2
Squaring a small number makes it very small indeed. If d1 and d2 are
already 0.01, then xoring b1 and b2 together results in a random bit
noise level 0.0002. This leads to the following equation for the
amount of non-random noise defined as n(bits) given the number of bits
in the xor sum:
n(1) = d
n(2) = 2*n(1)^2 = 2*d^2
n(4) = 2*n(2)^2 = 2*(2*d^2)^2 = 2^3*d^4
n(8) = 2*n(4)^2 = 2*(2^3*d^4)^2 = 2^7*d^8
n(i) = 2^(i-1)*d^i =
Here's how you can use this equation. Lets say you believe you have
non-random noise levels of no more than d. You want the noise level
to be less than N. We want to compute the number of bits needed, i:
N = n(i) =
2*N = (2*d)^i
log(2*N) = i*log(2*d)
i = log(2*N)/log(2*d)
So, for example, if you feel your non-randomness per bit is less than 10%,
but you need less than 1 part per billion, we compute the number of bits
needed in the xor-sum:
i = log(2*10^-9)/log(2*.1) = 12.5
In other words, just xor together at least 13 bits.
Beer is proof that God loves us, and wants us to be happy.