A Study on Maximal Length Cellular Automata and Primitive Polynomials in G F(2)

摘要

The problems of deciding maximal length cellular automaton (CA) and deciding primitive polynomial in GF(2) are equivalent to each other. Only rules 90 and 150, however, can take part in the rule vectors of maximal length CAs. As there is no efficient algorithm to decide a maximal length CA, we search for a pattern, if exists, in the rule vector of maximal length CAs. In this paper, we adopt three experimental approaches to observe any pattern in the CAs. First one is machine learning based approach. In the second approach, we test if the ratio of rules 90 and 150 matters. Finally, we concatenate n and m-cell CAs to get an (n + m)-cell CA and test it any inference can be drawn. Although, we receive no clear pattern in the rule vectors of maximal length CAs, the chance of (n + m)-cell CA to be maximal become high if small sized CAs are maximal length CAs.