Representing circular bitwise shift mathematically

Question

If you wanted to represent,

A -> B. B -> A,

you could easily represent it by matrix multiplication.

But for nonlinear operations like circular bitwise shifts, is there any nice mathematical representation that can be manipulated easily?

Answer 1

Sure. Multiplication by a permutation matrix will permute the entries of a vector in any fashion, circular bitwise shift among others. For instance... $$ \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} a_1 \\ a_2 \\ a_3 \end{pmatrix} = \begin{pmatrix} a_3 \\ a_1 \\ a_2 \end{pmatrix}$$

Answer 2

Assuming you're working with $m$-bit unsigned integers, the left circular shift is $x \to 2 x + (1-2^m)\ {\rm floor}(x/2^{m-1})$

Answer 3

Yet another representation is to view the bitwise rotation as multiplication by $X$ in the quotient ring $\mathbb F_2[X]/(X^{32}-1)$, for the appropriate value of $32$.

Of course, this ring has little to do with most other aritmetic operations (except that its addition corresponds to bitwise XOR). This lack of a straightforward connection is inherent in the operations, I think. Cryptographers use it deliberately to frustrate attacks such as linear cryptanalysis.