Reversibility of 1D Linear Cellular Automata with Radius 2 under Reflective Boundary Conditions

Reversibility is a fundamental property of cellular automata (CA) and plays an important role in applications such as cryptography, image security, and pseudo-random number generation. In this paper, we investigate the reversibility of one-dimensional (1D) linear cellular automata (LCA) with radius 2 under reflective boundary conditions (RBC) over a finite field [Formula: see text]. By representing the local rule with a reflective pentadiagonal rule matrix, the reversibility problem is transformed into determining whether the determinant of the corresponding rule matrix is nonzero. We derive a determinant decomposition formula and establish a sixth-order homogeneous linear recurrence relation satisfied by the determinant sequence. Based on this recurrence relation, a fast binary exponentiation (FBE) algorithm is proposed to determine the reversibility of large-scale LCA, reducing the computational complexity from [Formula: see text] of conventional Gaussian elimination to [Formula: see text] with constant space complexity. Furthermore, exploiting the periodicity of linear recurrence sequences over finite fields, a periodicity scale-reduction (PSR) algorithm is developed, which further reduces the complexity to [Formula: see text], where [Formula: see text] is the period determined by the characteristic polynomial of the recurrence. Numerical experiments over [Formula: see text] demonstrate the effectiveness of the proposed methods and reveal the periodic characteristics of reversibility for different local rules. The proposed framework provides an efficient algebraic approach for analyzing the reversibility of large-scale one-dimensional LCA under reflective boundary conditions.