Difference between revisions of "ApCoCoALib:RingF16"

From ApCoCoAWiki
m (New page: {{stub}} ==about== ApCoCoA will soon contain an implementation of the field <math>\mathbb{F}_16</math> The field is constructed via <math>\mathbb{F}_16 = \mathbb{F}[u]/(x^4 + x^3 + 1)</m...)
 
(updated / rewritten.)
 
(15 intermediate revisions 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.
−
ApCoCoA will soon contain 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}[u]/(x^4 + x^3 + 1)</math>.
 
−
The field's elements are represented as integers between 0 and 15. The corresponding mapping is the substituion homomorphism, mapping x to 2. Therefore we have e.g. <math>x^3 + x + 1 \mapsto 2^3 + x + 1 = 8 + 2  + 1 = 11</math>
 
  
−
==alternative representations==
+
Internally, the fields elements are stored as numbers
−
Instead of using <math>x^4 + x^3 + 1 </math>, we could have also chosen another irreducible polynomial of degree 4.
+
(unsigned char's, to be specific). These numbers, interpreted as bit-streams,
−
In total, there are three ireducible ones, namely <math>\{x^4 + x^3 + 1,x^4 + x^3 + 1, x^4 + x^3 + x^2 + x + 1 \}</math>
+
correspond to the univariate polynomial's sequence of coefficients. For example
−
If you have a system, which is based on one of the other irreducibly polynomials, you have to construct an isomorphism between the different representations of the field (which is unique). These isomorphisms can be constructed by mapping the irreducible polynomial's roots to the roots of
+
11 = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 <-> (1011)
−
x^4 + x^3 + 1, respecting the fields galois-group.  
+
        <-> 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'.
  
−
The irreducible polynomials and roots are:
+
An instance of RingF16 can be created via
−
[x^4 + x^3 + 1, [x^2, x, x^3 + x^2 + x, x^3 + 1]]
 
−
[x^4 + x + 1, [x^2, x, x^2 + 1, x + 1]]
 
−
[x^4 + x^3 + x^2 + x + 1, [x^3, x^2, x, x^3 + x^2 + x + 1]]
 
  
−
They were produced with the CoCoA4 code, explained [[constructing_fields|here]].
+
  CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF16();
  
−
[[Category::ApCoCoA]][[Category:HowTo]][[Category:characteristic_2]]
+
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]]
 +
__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"