Inverting a large circulant Boolean matrix?

What are efficient methods for inverting a (possibly large) circulant Boolean matrix (and determining if that's possible)? The given and result are defined by their first column (or, within order, row) of $n$ Boolean elements.

Recall that a circulant matrix is a square matrix where each row is the previous rotated by one to the right.

The motivating context is cryptography.

The matrix vector product is the same as multiplying polynomials with the matrix row elements resp. vector components as coefficients, modulo $z^n-1$. Thus the equation $$a(z)·u(z)\equiv 1\pmod {z^n-1}$$ can be rewritten as Bezoutian identity $$a(z)·u(z)+(z^n-1)·v(z)=1$$ which is exactly the result of the XGCD.
• Ah ! So the problem can be solved by finding inverse modulo $z^n+1$, using the Extended Euclidean algorithm for Boolean polynomials. That's clear now. – fgrieu Jun 9 '17 at 11:11