ApCoCoALib:RingF8

User documentation for files RingF8.C and RingF8.H

These files contain an implementation of the field with 8 elements. The fields representation is ((Z/(2))[x])/(x^3 + x + 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

6 =  1*2^2 + 1*2^1 + 0*2^0 <-> (110)
       <-> 1*x^2 + 1*x^1 + 0*x^0 = x^2 + x

So the field element x^2 + x is internally stored as '6'.

An instance of RingF8 can be created via

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

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

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

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

  CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF8();
  CoCoA::RingElem e(r,6);

and e represents the ring element 'x^2+x' or equivalently '6'. 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 RingF8.C and RingF8.H

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

To multiply a and b, we split a into its exponents (a_0, ... a_2) and XOR the elements {m_(i,b) | i=0,..2, 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,..2, a_i =1 } of the division matrix.

Other options would be the usage of a logarithmic matrices or two 'full' 8 times 8 matrices. 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. Since a 3 times 8 matrix of unsigned chars is rather small, here do not occur any paging conflicts, but eventually a 8 times 8 matrix could be more efficient.

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_8 or to map elements in Z[x] or Z/(2)[x] into F_8.

Also isomorphisms between different representations of F_8 could be implemented. Any irreducible polynomial of degree 3 in Z/(2)[x] can be used to create a representation of F_8. Based in the galois group of F_8 and the irreducible polynomial's roots in F_8 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.