On the different notions of pseudorandomness

Abstract

This article explains the various notions of pseudorandomness, like Martin-L öf randomness, Kolmogorov complexity, Shannon entropy and quasi-randomness. We describe interconnections between these notions and describe how the non-computable notions among them are relaxed and used in practice, for example in statistics or cryptography. We give examples for pseudorandom generators relating to these notions and list some dependencies between the quality of pseudorandom numbers and its impact on some properties of randomized algorithms using them.