1
$\begingroup$

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?

3 Answers 3

3

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}$

  • 1
    Otherwise known as the basic circulant permutation matrix.2011-11-17
3

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})$

  • 0
    I think I get it, it makes more sense to me if the floor is multiplied out so you get $floor(x/2^{m-1}) - 2^mfloor(x/2^{m-1})$. It's a conditional add of$1$to flip the bit in the lowest place if needed, and a conditional subtraction of the $2^m$ if it was needed. It'd be even clearer if we stored $floor(x/2^{m-1})$ in value called 'highbitset' ;) That's nifty.2012-10-16
1

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.

  • 0
    True, it's not a field. But so what? I didn't claim it was.2012-11-19