ApCoCoALib:RingF2048

User documentation for files RingF2048.C and RingF2048.H

These files contain an implementation of the field with 2048 elements. The fields representation is ((Z/(2))[x])/(x^11 +x^3 + x^5 +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 <-> (00000001011)
       <->  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 RingF2048 can be created via

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

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

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

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

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

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

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

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

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