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.
$\begingroup$
$\endgroup$
-
1$\begingroup$ What is your understanding of addition in a finite field? $\endgroup$ – Yuval Filmus Apr 13 '20 at 16:05
-
2$\begingroup$ There's nothing special about the 8. $\endgroup$ – Yuval Filmus Apr 13 '20 at 16:07
-
$\begingroup$ @YuvalFilmus My understanding is rough but it's that they're an extension of finite rings where the number of elements is a power of the prime (including the prime itself), what this means in practice is something I have little understanding of $\endgroup$ – Faissaloo Apr 13 '20 at 17:05
$\begingroup$
$\endgroup$
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$.
answered Apr 13 '20 at 16:07
-
$\begingroup$ I have some questions: Why does
1+x^2correspond to0b101? Why does XOR correspond to elementwise addition? Why isn't a carry possible? $\endgroup$ – Faissaloo Apr 13 '20 at 17:09 -
1$\begingroup$ The bits in the binary representation are the coefficients of $1,x,x^2,x^3$ and so on. Addition is just addition of polynomials, that is, addition in $GF(2)[x]$. The coefficients of each $x^i$ are added separately. I don't see where a carry would come in. $\endgroup$ – Yuval Filmus Apr 13 '20 at 17:22
-
$\begingroup$ I think I see what you're trying to say, so 101 is in fact the representation of
1x^0+ 0x^1 + 0x^2but you've written the simplified version correct? With this information now the addition stuff makes sense $\endgroup$ – Faissaloo Apr 13 '20 at 18:25
