The Rotate and Shift operations in a Finite Field

Question

Do the Rotate and Shift operations in $GF_2$ have simple expressions in a finite field?

The Rotate operation $ROT[x,n]$ left rotates by n-bits. So $ROT[(0,1,1,1),2]=(1,1,0,1)$.

The Shift operation $SHIFT[x,n]$ left shifts by n-bits. So $SHIFT[(0,1,1,1),2]=(1,1,0,0)$.

So for SHIFT, a n-right shift is the same thing as multiplication by 2^n... at least in the binary integer world. For example: $37=(1,0,0,1,0,1)_2$ and $37*2^2=148=(1,0,0,1,0,1,0,0)_2$... Now since the number of digits in 37 was initially 6 and we are therefore bounded by $2^6$, $148=(0,1,0,1,0,0)$ which is the right shift of $37$ by $2$ to the right.

Answer 1

There is no expression in what you call $GF_2$ per se for shifting a sequence of bits (elements of $GF_2$) cyclically (or rotating it) for the simple reason that the sequence is not an element of $GF_2$; the individual components (bits comprising the sequence) are in $GF_2$, but not the sequence itself. Now, if you interpret the $n$-bit sequence $(c_{n-1},c_{n-2}, \ldots, c_1, c_0)$ as the integer $C = \sum_{i=0}^{n-1} c_i 2^i$, then it is true that a rotation by $k$ places, $0 \leq k < n$, that is, $$(c_{n-1},c_{n-2}, \ldots, c_1, c_0) \longrightarrow (c_{n-k-1}, c_{n-k-2}, \ldots, c_0,c_{n-1}, c_{n-2}, \ldots, c_{n-k})$$ gives the sequence corresponding to the integer $D^{(k)}$ where $$D^{(k)} = \begin{cases}2^kC \bmod (2^n-1), & C \neq 2^n-1,\\ 2^n-1, & C = 2^n-1,\end{cases}$$ but this is not an operation in the finite field $GF_2$. Note that the special calculation for $(1,1,\ldots 1) \leftrightarrow C=2^n-1$ is needed to avoid getting a $0$ result when the mod $2^n-1$ operation is carried out on $2^k(2^n-1)$.

Try it, you will like it. Your $ROT[(0,1,1,1),2]=(1,1,0,1)$ corresponds to $7$ being transformed to $2^2\times 7 = 28 \equiv 13 \bmod 15.$

Alternatively, if you interpret the sequence as the coefficients of a polynomial $C(x) = \sum_{i=0}^{n-1}c_i x^i$, then rotating by $k$ bits results in the bit sequence corresponding to the polynomial $$D^{(k)}(x) = x^k C(x) \bmod (x^n-1)$$ where both $C(x)$ and $D^{(k)}(x)$ belong to a mathematical structure denoted by $\mathbb F_2[x]$ and called the ring of polynomials in $x$ with coefficients in $\mathbb F_2 = GF_2$. Once again, these polynomials are not "in" $GF_2$.

Answer 2

These operations aren't well-defined on a finite field $\mathbb{F}_{2^n}$ in the first place. To define them you need to pick an encoding of elements of $\mathbb{F}_{2^n}$ as strings of $n$ bits, and there isn't a distinguished such encoding; you get such an encoding from any basis of $\mathbb{F}_{2^n}$ as a vector space over $\mathbb{F}_2$, but there isn't a distinguished basis, and there are other encodings that don't even have this form.