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

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 2n - 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. © 2026 Binghamton University Libraries. All rights reserved.