1

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?

countunique
  • 2,449

3 Answers3

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

Dimitrije Kostic
  • 1,550
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})$

Robert Israel
  • 448,999
  • 1
    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. – Joseph Garvin Oct 16 '12 at 02:55
  • 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. – Joseph Garvin Oct 16 '12 at 02:57
  • 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). – Robert Israel Oct 16 '12 at 05:54
  • 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. – Joseph Garvin Oct 16 '12 at 17:29
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.

hmakholm left over Monica
  • 286,031