Exploring Maximal Length Cellular Automata to Generate Primitive Polynomials in GF(2)

Authors

• Sumit Adak, DTU - Technical University of DenmarkFollow
• Subhrajit Deb, Indian Institute of Engineering Science and Technology, Shibpur, IndiaFollow
• Anurag Ghosh, Indian Institute of Engineering Science and Technology, Shibpur, IndiaFollow
• Angshuman Roy, Indian Institute of Engineering Science and Technology, Shibpur, IndiaFollow
• Souvik Roy, School of Engineering and Applied Science, Ahmedabad University, Gujarat, IndiaFollow

Author ORCID Identifier

0000-0002-1814-7612

Abstract

We present a simple method that uses cellular automata (CAs) to find primitive polynomials over GF(2). We used maximal length CAs as tools to generate primitive polynomials. It is usually very difficult to find maximal length CAs or primitive polynomials since they require exponential time, and there is no linear time method. However, in our work, given an n-size specific sequence of CA with reasonable probability, our technique computes a cycle of length at most 2^n-1 (maximal length) in O(n) time. The characteristic polynomials of synthesized maximal length CAs are claimed to be primitive since it was previously established that the characteristic polynomial of a maximal length CA is primitive.

Recommended Citation

Adak, Sumit; Deb, Subhrajit; Ghosh, Anurag; Roy, Angshuman; and Roy, Souvik (2026) "Exploring Maximal Length Cellular Automata to Generate Primitive Polynomials in GF(2)," Northeast Journal of Complex Systems (NEJCS): Vol. 8 : No. 3 , Article 3.
DOI: https://doi.org/10.63562/2577-8439.1145
Available at: https://orb.binghamton.edu/nejcs/vol8/iss3/3