2
$\begingroup$

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.

$\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
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I have some questions: Why does 1+x^2 correspond to 0b101? 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^2 but you've written the simplified version correct? With this information now the addition stuff makes sense $\endgroup$ – Faissaloo Apr 13 '20 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.