0
$\begingroup$

This question already has an answer here:

The wikipedia.org article on Finite field arithmetic provides an example of multiplying $83$ and $206$ in $\mathbb{F}_{2^8}$ with $x^8+x^4+x^3+x+1$ as the reducing polynomial (in fact it is the reducing polynomial for AES). Quoting it:

Multiplying $83$ and $206$, whilst ignoring the carries, yields $16,254$ or (in binary) 11111101111110.

The reducing polynomial is then converted to binary (100011011), shifted forward to match the length of the number being reduced (eg. multiplied by a power of two) and then XOR'd (subtracted) against the number to be reduced. It seems like it's supposed to do this until the number being reduced is less than the reducing polynomial (in binary).

Here's the example wikipedia gives:

      11111101111110 (mod) 100011011
     ^100011011     
       1110000011110
      ^100011011    
        110110101110
       ^100011011   
         10101110110
        ^100011011  
          0100011010
          ^100011011 
            00000001

My question is... why is the last XOR done? 0100011010 is less than 100011011..

$\endgroup$

marked as duplicate by Biv, e-sushi Jul 7 '17 at 20:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

The last XOR is done, to get rid of the $x^8$ term. Polynomials in $GF(2^n)$ do have a maximum degree of $n-1$.

$\endgroup$

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