random-number-generator

Survey about Randomness and RNGs + Implementation of some famous algorithms (LFSR, NLFSR, Berlekamp-Massey)

Personal work for the seminar The Art of Mathematical Computing (Universität Passau, Faculty of Computer Science, Summer 2014).

Abstract

This survey focus on Random Number Generators (RNGs). In this light, it first attempts to unravel the various definitions of randomness and pseudo-randomness, before detailing the different categories of random generators, based on physical phenomena or computations. Emphasis is put on Linear- and Non-Linear Feedback Shift Registers (LFSRs and NLFSRs), and their implementation. Finally, the difficulty of objectively testing RNGs is discussed, and various test suites are described.

##Keywords: RNG, randomness, entropy, pseudorandom, LFSR, NLFSR, test suite, Berlekamp-Massey algorithm

References

1. Downey, R.: Some recent progress in algorithmic randomness. In Mathematical Foundations of Computer Science 2004. Springer Berlin Heidelberg (2004)
2. Wikipedia: Random Number Generation (2014)
3. Aumasson, J.P.: The Search and Construction of Nonlinear Feedback Shift Registers. AppSec Forum Switzerland 2013 (2013)
4. Raymond, S., Andrew, S., Patrick, C., Jason, M.: Linear Feedback Shift Register (2001)
5. Joux, A.: Algorithmic cryptanalysis. CRC Press (2009)
6. Szmidt, J.: The Search and Construction of Nonlinear Feedback Shift Registers. Military Communication Institute, Zegrze, Poland (2013)
7. Wikipedia: Linear Feedback Shift Register (2014)
8. Dubrova, E.: A List of Maximum Period NLFSRs. IACR Cryptology ePrint Archive 2012 (2012)
9. Ritter, T.: Randomness Tests: A Literature Survey (2007)
10. L'Ecuyer, P, S.R.: TestU01 - A Software Library in ANSI C for Empirical Testing of Random Number Generators (2002)
11. Marsaglia, G.: The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness (2005)
12. Soto, J.: Statistical Testing of Random Number Generators. Proceedings of the 22nd National Information Systems Security Conference NIST, 1999 (1999)
13. Berlekamp, E.R.: Nonbinary BCH decoding. University of North Carolina. Department of Statistics (1967)
14. Massey, J.L.: Shift-register synthesis and BCH decoding. Information Theory. IEEE Transactions 15(1) (1969)
15. Feng, G.-L., T.K.: A generalization of the Berlekamp-Massey algorithm for multisequence shift-register. Information Theory, IEEE Transactions 37(5) (2012)
16. Rodrigez, S.: Implementation of a decoding algorithm for codes from algebraic curves in the programming language Sage. diploma thesis, Faculty of San Diego State University (2013)