How to turn loaded dice into fair coins

We present a new technique for simulating fair coin flips using a biased, s tationary source of randomness. Sequences of random numbers are of pervasiv e importance in cryptography and vital to many other computing applications , Many sources of randomness, such as radioactive or quantum-mechanical sou l,ces, possess the property of stationarity, In other words, they produce i ndependent outputs over fixed probability distributions. The output of such sources may be viewed as the result of rolling a biased or loaded die. Whi le a biased die mag be a good source of entropy, many applications require input in the form of unbiased bits, rather than biased ones. For this reaso n, almost fifty years ago, von Neumann presented a now well-known and exten sively investigated technique for using a biased coin to simulate a fair co in. We describe a new generalization of von Neumann's algorithm distinguish ed by its high level of practicality and amenability to analysis, In contra st to previous efforts, we are able to prove our algorithm optimally effici ent, in the sense that it simulates the maximum possible number of fair coi n flips for a given number of die rolls, In fact, we are able to prove that in an asymptotic sense our algorithm extracts the full entropy of its inpu t. Moreover, we demonstrate experimentally that our algorithm achieves a hi gh level of computational and output efficiency in a practical setting.