Use coin flipping to make an arguably true random number generator
Most random number generation libraries are actually PRNGs (Pseudo Random Number Generators), since computers are basically deterministic. The library presented in this repository, however, uses the age-old concept of coin flipping along with naturally occuring delays, that occur on a multi-process system, to generate truly random numbers.
A tight loop which constantly flips a single bit (serving as a coin) is run for a millisecond. Since the number of times it would be able to flip the bit changes due to random fluctuations in time due to context switching of processes, this generates an arguably truly random bit (I would love to see a PoC that shows otherwise, however).
While it can be agreed that context switching is a deterministic process, we know that practically, the different clocks that exist due to the numerous hardware devices attached to a system, each run at a separate speed. This leads to differing boot times each time, even if hardware remains unchanged. Due to similar reasons, what would be deterministic (the context switching), now has an extra spanner thrown in its works: the clock skew. This means it would basically be impossible (again, I’d love for someone to prove me wrong) to recreate the exact conditions that led to the production of the said bit. This means that the bit is no longer deterministic. Hence, the bit is "truly" random.
Since the above generated bit might not actually have 50-50 probability of 0 and 1, we use the following table to normalize the probabilities. We repeatedly sample
get_bit() twice, and decide based upon the results.
|First Bit||Second Bit||Result|
Assuming that each bit from
get_bit() is independent of the previous bit,
get_fair_bit() will return a bit with 50-50 probability of 0 or 1
By concatenating 31 values from
get_fair_bit() , we get the binary representation of a number betweeen 0 and
TRUE_RAND_MAX (2147483647 = 2^32 – 1). This value is returned as a
long int , to get a signature similar to
Compile the code by running
make . This ends up creating a bunch of files:
Test the random number generator using
./tester . Generate an unending stream of data using
If you wish to use the generator in your own program, simply copy
true_random.h into your project, and use the
true_random() function after a
#include "true_random.h" .
This software is licensed under the MIT License
Run through standard RNG tests.