Sequences, randomness and security
Serdar Boztaş · 2013
The definition of of randomness and pseudorandomness in the context of sequence generation is far from controversial. We provide a survey of some approaches to randomness, including: 1. Information theoretic (i.e., probabilistic) approaches, such as those based on Shannon and Renyi entropies, and 2. Complexity theoretic approaches based essentially on Kolmogorov complexity. We discuss the settings where one approach may be superior to the other. We also consider the design and analysis of randomness tests, illustrating it with some examples.