Abstract: When constructing random number generators based on physical processes, it is usually not possible to get uniformly and independently distributed output bits. We therefore present a method for postprocessing the output of the random source and generating good randomness, we call that method the adaptive extraction. Its two main features are: First, we do not need to know the source's behaviour in every detail (i.e. it suffices to put some constraints on the distribution of the output). Secondly, the amount of generated good randomness (i.e. nearly uniformly distributed data) is automatically adapted to the quality of the input.
We then present a technique for modelling sources, similar to hidden Markov models, which is especially suited for use with the adaptive extraction.
Finally we investigate some practical aspects of our theory: We present a statistical test to verify assumptions made on the source, and we examine a given physical source with respect to the feasibility of adaptive extraction.
Permalink: http://www.ut.ee/~unruh/publications/unruh03zufallsextraktoren.html