ApCoCoALib:RingF512

User documentation for files RingF512.C and RingF512.H

These files contain an implementation of the field with 512 elements. The fields representation is ((Z/(2))[x])/((x^9 + x +1).

Internally, the fields elements are stored as numbers (unsigned integers, 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 <-> (000001011)
       <->  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::NewRingF512();

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

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

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

  CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF512();
  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 RingF512.C and RingF512.H

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

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

Other options would be the usage of a logarithmic matrices or two 'full' 512 times 512 matrices or a double logarithmic 9 times 9 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_512 or to map elements in Z[x] or Z/(2)[x] into F_512.

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