Slashdot Comments We Liked

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.

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 = .5*2^i*d^i = .5*(2*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) = .5*(2*d)^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.