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

  • 2
    In general, the circular bitwise shift matrix of any size will have 1's on the super diagonal, a 1 in the lower lefthand corner, and 0's elsewhere.2011-11-15
  • 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
    Could you explain how you derived this? Based on how left circular shift is usually implemented in code, ((x << 1) | (x >> (m - 1))), I can see the $2x$ as being the left shift, but I'm confused how the rest becomes equivalent to the right shift and the bitwise or. $floor(x/2^{m−1})$ will only ever be 0 or 1, since in the m-bit unsigned integers nothing is twice as big as $2^{m−1}$ since it wraps to 0. So we're conditionally deciding whether to add $(1−2^m)$ based on whether our starting value is greater than $2^{m−1}$. But passed that I'm not sure why adding $(1−2^m)$ does the trick.2012-10-16
  • 0
    I get that checking for the value being bigger than $2^{m-1}$ is checking whether the high bit is set, and I get that because we did $2x$ not modulo we need to somehow cancel out the 1 that may be in the 33rd bit, and somehow set the least significant bit, but that addition appears to kill two birds with one stone somehow.2012-10-16
  • 0
    When the "high bit" was set, we need to subtract $2^m$ (to get rid of the high bit after the left shift) and add $1$ (to put that bit back in the low bit).2012-10-16
  • 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