Difference between revisions of "ApCoCoALib:RingF16"

From ApCoCoAWiki
(update wtr. the implementation of F16.)
(updated / rewritten.)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
−
{{stub}}
+
==User documentation for files RingF16.C and RingF16.H==
  
−
==about==
+
These files contain an implementation of the field with 16 elements.
−
ApCoCoALib  contains an implementation of the field <math>\mathbb{F}_{16}</math>
+
The fields representation is ((Z/(2))[x])/(x^4 + x^3 +1).
−
The field is constructed via  <math>\mathbb{F}_{16} = \mathbb{F}[x]/(x^4 + x^3 + 1)</math>.
 
−
The field's elements are represented as integers between 0 and 15.  The corresponding mapping is the substitution homomorphism, mapping x to 2. Therefore we have e.g. <math>x^3 + x + 1 \mapsto 2^3 + 2^1 + 2^0 = 8 + 2  + 1 = 11</math>
 
  
−
This implementation is contained in the files RingF16,[CH]. A new instance can be created with the command:
+
Internally, the fields elements are stored as numbers
−
  ApCoCoA::AlgebraicCore::NewRingF16();
+
(unsigned char's, 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 <-> (1011)
 +
        <-> 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 example, describing how to use RingF16, especially together with ring homomorphisms can be found in ApCoCoALib's example directory. It is named ex-RingF16.C
+
An instance of RingF16 can be created via
 +
 
 +
  CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF16();
 +
 
 +
To see if a given CoCoA::ring R is an instance of RingF16 you can check
 +
 
 +
  bool b = ApCoCoa::AlgebraicCore::IsRingF16(R);
 +
 
 +
Furthermore, any instance of RingF16 can be used like any other ring in CoCoA.
 +
To create an element proceed as follows:
 +
 +
  CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF16();
 +
  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 RingF16.C and RingF16.H==
 +
 
 +
Currently, this fields uses 'semi-logarithmic' multiplication and division
 +
matrixes. This means both matrices are of size 4 times 16.
 +
 
 +
To multiply a and b, we split a into its exponents (a_0, ... a_3) and
 +
XOR the elements {m_(i,b) | i=0,..3, 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,..3, a_i =1 } of the division matrix.
 +
 
 +
Other options would be the usage of a logarithmic matrices or two 'full'
 +
16 times 16 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 4 times 16 matrix of unsigned chars
 +
is rather small, here do not occur any paging conflicts, but eventually
 +
a 16 times 16 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_16 or to map elements in Z[x]
 +
or Z/(2)[x] into F_16.
 +
 
 +
Also isomorphisms between different representations of F_16 could be
 +
implemented.  Any irreducible polynomial of degree 4 in Z/(2)[x] can be used
 +
to create a representation of F_16. Based in the galois group of F_16 and the
 +
irreducible polynomial's roots in F_16 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 http://apcocoa.org/wiki/ApCoCoA:Representation_of_finite_fields]] - more
 +
information on the representation of finite fields..
 +
 
 +
[[http://apcocoa.org/wiki/HowTo:Construct_fields http://apcocoa.org/wiki/HowTo:Construct_fields]] - a description, how the
 +
multiplication / division matrices were constructed, including the needed
 +
source-code / tools.
  
  
 
[[Category:ApCoCoALib_Manual]]
 
[[Category:ApCoCoALib_Manual]]
 +
__NOTOC__

Latest revision as of 17:14, 6 March 2008

User documentation for files RingF16.C and RingF16.H

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

11 = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 <-> (1011)
       <-> 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 RingF16 can be created via 

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

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

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

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

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

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

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

Other options would be the usage of a logarithmic matrices or two 'full' 16 times 16 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 4 times 16 matrix of unsigned chars is rather small, here do not occur any paging conflicts, but eventually a 16 times 16 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_16 or to map elements in Z[x] or Z/(2)[x] into F_16.

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

Retrieved from "http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoALib:RingF16&oldid=7362"