1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

You can use the extended Euclidean algorithm for polynomials.

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fgrieu Jun 9 '17 at 11:11
  • 1
    $\begingroup$ Yes, exactly that. One has at first to be careful in the encoding from matrix to polynomial, order of coefficients and index shifts, so that the results on the coefficients are identical. $\endgroup$ – Lutz Lehmann Jun 9 '17 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.