ApCoCoALib:RingF4096

From ApCoCoAWiki
Revision as of 17:35, 6 March 2008 by Dheldt (talk | contribs) (initial push in)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

User documentation for files RingF4096.C and RingF4096.H

These files contain an implementation of the field with 4096 elements. The fields representation is ((Z/(2))[x])/(x^12 +x^4 + 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 <-> (000000001011)
       <->  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 RingF4096 can be created via

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

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

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

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

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

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

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

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

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