Generating quasi-random sequences from semi-random sources

摘要

We consider mathematically the problem of generating random bit-sequences from physical noise sources (such as zener diodes). We propose a very general mathematical model for such physical sources: the semi-random source, and show how to convert the output of such sources into quasi-random sequences. Such sequences are indistinguishable from truly random ones in a strong sense. This enables us to prove that quasi-random sequences can be used in place of truly random ones for applications such as seeds for pseudo-random number generators, randomizing algorithms, and stochastic simulation experiments.