relations of galois field to bitoperators in C

Question

Are bit operators in C corelated somehow to Galois field. Is there any literature (or beginner tutorials) on it?

Answer 1

XORing (a = b ^ c) of $n$-bit values corresponds to addition of vectors in $\Bbb F_2^n$. Since $\Bbb F_{2^n}\cong \Bbb F_2^n$ as vector spaces over $\Bbb F_2$, this also emulates addition in $\Bbb F_{2^n}$. Multiplication in $\Bbb F_{2^n}$ is a whole different story, and other bit operations (&, |) do not have such a nice interpretation.

Answer 2

As Hagen von Eitzen points out, the bitwise XOR operator ^ corresponds to addition in $\mathbb F_{2^n}$, while the other bitwise operators & and | do not.

Two other bitwise operators (the shift operators >> and <<) also can be viewed as providing some support for operations in $\mathbb F_{2^n}$. Think of $\mathbb F_{2^n}$ as the set of binary polynomials of degree less than $n$ with field addition and field multiplication being polynomial addition and multiplication modulo an irreducible polynomial $p(x)$ of degree $n$. Then, for example, if $1011$ corresponds to the polynomial in $x^3+x+1$ in $\mathbb F_{2^4}$, the left shift operator applied to $1011$ yields $10110 \leftrightarrow x^4+x^2+x$, that is, multiplication of $x^3+x+1$ by $x$ while the right shift operator yields $101 \leftrightarrow x^2+1$, that is, the quotient when $x^3+x+1$ is divided by $x$.

Thus, the shift operators operators can be used (in conjunction with ^) to write subroutines for multiplication and division in $\mathbb F_{2^n} = \mathbb F_2[x]/\langle p(x)\rangle$.