Non-uniform nonlinear cellular automata with large cycles and their application in pseudo-random number generation

Sukanya Mukherjee (), Sumit Adak (), Kamalika Bhattacharjee and Sukanta Das ()
Additional contact information
Sukanya Mukherjee: Department of Computer Science and Engineering, Institute of Engineering and Management, Kolkata 700 091, West Bengal, India
Sumit Adak: Department of Information Technology, Indian Institute of Engineering Science and Technology, Shibpur, P.O. Botanic Garden, Howrah, West Bengal 711103, India
Kamalika Bhattacharjee: Department of Computer Science and Engineering, National Institute of Technology, Tiruchirappalli, Tamil Nadu 620015, India
Sukanta Das: Department of Information Technology, Indian Institute of Engineering Science and Technology, Shibpur, P.O. Botanic Garden, Howrah, West Bengal 711103, India

International Journal of Modern Physics C (IJMPC), 2021, vol. 32, issue 07, 1-30

Abstract: This paper reports a stochastic method of synthesizing three-neighborhood two-state nonlinear non-uniform reversible cellular automata (CAs) having large cycle(s). To develop this method, we propose a parameter which measures the dependency of each cell on its neighbors. Using this parameter, we classify the possible rules of reversible CAs into four classes — completely dependent, partially dependent, weakly dependent and independent. A CA is expected to have larger cycle length if most of the rules of the CA are sensitive to their neighbors; hence, possess higher parameter value. It is shown that our synthesis algorithm, where rules are selected from the first three classes based on Gaussian distribution, can successfully generate CAs having desired length cycle. We empirically show that most of the synthesized CAs have a cycle at least as large as 2n−1, where n is the lattice size. Then, as an application of such CAs, a scheme is developed to design window-based pseudo-random number generators (PRNGs) using (some of) them. These PRNGs are easily implementable on hardware and are highly portable. Finally, when compared on the same platform, our PRNGs outperform most of the well-known PRNGs existing today.

Keywords: Cellular automaton (CA); reversibility; nonlinearity; large length cycle; degree of dependence; pseudo-random number generator (PRNG) (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183121500911
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:32:y:2021:i:07:n:s0129183121500911

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183121500911

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().