ApCoCoALib:RingF16: Difference between revisions

From ApCoCoAWiki
Dheldt (talk | contribs)
638 edits
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...
 
Dheldt (talk | contribs)
638 edits
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 "https://app.apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoALib:RingF16&oldid=7362"