Computing over F₂₅₆

The field with 256 elements is isomorphic to the set of polynomials modulo p(X)=X⁸+X⁷+X²+X+1 in F₂[X] où F₂ is the field with 2 elements (integers modulo 2). We denote by One could replace p(X) by any other irreducible polynomial of degree 8 over F₂[X]. Here, p(X) has an additional property, it is primitive, which means that any polynomial of degree no more than 7 is a remainder of a Xⁱ modulo p(X) for some i. In practice, this provides us with two representations of elements of the field, which are complementary to perform additions and multiplications.

• Multiplication and division using the exponent representation: the monomial Xⁱ is represented by the integer i.
  F₂₅₆ = {0} U {Xⁱ | 0 <= i <= 254 }
  By convention, one represents the 0 element by -1. The multiplication is straightforward: if [i] is the field element represented by the integer i, we have

  [i] × [j] =

  [ [ [

  [-1] si i=-1 ou j=-1 [i+j mod 255] sinon


For the division : 1/[i] = [255-i] (provided i !=-1 )

• Addition and soustraction using the second representation based on polynomials with 0-1 coefficients
  F₂₅₆ = {f(X) over F₂[X] with deg f < 8 }
  Any polynomial is represented by its value in X=2 in Z (i.e. the integer which base 2 expansion is the list of coefficients of the polynomial). Addition is straightforward: noting (i) the field element represented by the integer i, we have
  (i) + (j) = (i ^ j)
  where operator ^ is the « exclusive or »

Another option for addition is to tabulate values of (1+ [k]) for any non-zero [k] (ie k != -1);
Indeed, let TabXplusUn(k) = j with [j] = 1+[k].
Then, we have, for j >=i et i!=-1:
[i]+[j] = [i]*(1 + [j]/[i]) = [i] * ( 1+ [j-i mod 255] ) = [i]*[TabXplusUn(j-i)] = [ i + TabXplusUn(j-i) mod 255 ]

In practice, for a small field (as here with only 256 elements), the tabulation is the best option.