ApCoCoALib:RingF1024

User documentation for files RingF1024.C and RingF1024.H

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

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

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

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

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

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

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

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

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

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