ApCoCoALib:RingF256

User documentation for files RingF256.C and RingF256.H

These files contain an implementation of the field with 256 elements. The fields representation is ((Z/(2))[x])/(x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1).

Internally, the fields elements are stored as numbers (unsigned char's, to be specific). These numbers, interpreted as bit-streams, correspond to the univariate polynomial's sequence of coefficients. For example

11 = 1* 2^3 + 0*2^2 + 1*2^1 + 1*2^0 <-> (00001011)
       <-> 0*x^7+ 0*x^6  + 0*x^5 + 0*x^4 + 1*x^3 + 0*x^2 + 1*x^1 + 1*x^0
	 = x^3 + x + 1

So the field element x^3 + x + 1 is internally stored as '11'.

An instance of RingF256 can be created via

  CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF256();

To see if a given CoCoA::ring R is an instance of RingF256 you can check

  bool b = ApCoCoa::AlgebraicCore::IsRingF256(R);

Furthermore, any instance of RingF256 can be used like any other ring in CoCoA. To create an element proceed as follows:

  CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF256();
  CoCoA::RingElem e(r,11);

and e represents the ring element 'x^3+x+1' or equivalently '11'. A warning: adding the element '3' to the element '2' does NOT lead to the element '5', since '3' <-> 'x+1', '2' <-> 'x' and (x+1) + (x) = 1 <-> '1'. Some more details on how elements can be stored and retrieved from this ring can be found in the example ex-RingF16.C in ApCoCoALib's example directory.

Maintainer documentation for files RingF256.C and RingF256.H

Currently, this fields uses 'semi-logarithmic' multiplication and division matrixes. This means both matrices are of size 8 times 256.

To multiply a and b, we split a into its exponents (a_0, ... a_7) and XOR the elements {m_(i,b) | i=0,..7, a_i =1 } of the multiplication matrix.

To divide a through b, we again split a like above and XOR the elements {d_(i,b) | i=0,..7, a_i =1 } of the division matrix.

Other options would be the usage of a logarithmic matrices or two 'full' 256 times 256 matrices or a double logarithmic 8 times 8 one. So we have to make a decision between XOR operations and memory usage. Which of this versions is optimal has to be checked for different problem settings.

Bugs, Shortcomings and other ideas

The current implementation does not support a lot of intractability with other rings. A set of Ringhomomorphisms could be implemented to allow a more easy switch between other representations of F_256 or to map elements in Z[x] or Z/(2)[x] into F_256.

Also isomorphisms between different representations of F_256 could be implemented. Any irreducible polynomial of degree 8 in Z/(2)[x] can be used to create a representation of F_256. Based in the galois group of F_256 and the irreducible polynomial's roots in F_256 an isomorphism can be described, mapping one representation to another. This might be handy, if a special modulus is given for a computation which is not the one, used for this implementations multiplication / division matrices.

References

[http://apcocoa.org/wiki/ApCoCoA:Representation_of_finite_fields] - more information on the representation of finite fields..

[http://apcocoa.org/wiki/HowTo:Construct_fields] - a description, how the multiplication / division matrices were constructed, including the needed source-code / tools.