HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is addition in GF(2^8) the same as XOR?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
xorwhythesameaddition

Problem

I get the impression it has to do with either some quirk involved with limiting to 2^8 or that I'm misunderstanding what addition can be within the context of a finite field, but I'm not quite sure why it's described as 'addition' in the literature I read but the code I see implements it with XOR.

Solution

Finite fields are usually described as polynomials over the base field (in this case $GF(2)$) modulo some irreducible polynomial. If you represent each polynomial as a vector of coefficients, then addition of polynomials corresponds to elementwise addition of the coefficients, which in the case of $GF(2)$, translates to XOR.

For example, suppose that your field elements are $1+x^2$ and $x+x^2 + x^5$. Their binary representations are $101$ and $100110$ (LSB is the coefficient of $1$). Their sum is $1+x+2x^2+x^5 = 1+x+x^5$ (since $2=0$ over $GF(2)$), whose binary representation is $100011$. This is the XOR of $101$ and $100110$.

Context

StackExchange Computer Science Q#124048, answer score: 4

Revisions (0)

No revisions yet.