Study of First Degree Cellular Automata for Randomness
Kamalika Bhattacharjee and Vicky Vikrant
This paper discusses the potentiality of Cellular Automata (CAs) represented by first degree equations as source of randomness. These CAs are identified by eight constants, named as Parameters of First Degree CA. A greedy filtering technique is developed that uses existing chaotic parameters to identify the candidate CAs. Based on a theoretical strategy and experimental verification, a list of good first degree CA parameters are identified which remains as excellent source of randomness irrespective of change in number of states. Finally, we use these CAs as pseudo-random number generators.
Keywords: Cellular automata (CAs), first degree CAs, chaotic parameters, space-time diagram, pseudo-random number generator (PRNG), diehard, TestU01, NIST