Inversion of two level Circulant Matrices over Zp

We consider the problem of inverting block circulant with circulant blocks BCCB matrices with entries over the field $\Zp$. This problem arises in the study of of two-dimensional linear cellular automata. Since the standard reduction to diagonal form by means of FFT has some drawbacks when working over $\Zp$, we solve this problem by transforming it into the equivalent problem of inverting a circulant matrix with entries over a suitable ring~$\R$. We show that a BCCB matrix of size $mn$ can be inverted in $\O{m n\, c(m,n)}$ operations in $\Zp$, where $c$ is a low degree polynomial in $\log m$ and $\log n$.