http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoALib:RingF256&feed=atom&action=historyApCoCoALib:RingF256 - Revision history2022-10-04T06:07:14ZRevision history for this page on the wikiMediaWiki 1.35.0http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoALib:RingF256&diff=7367&oldid=prevDheldt: initial push in.2008-03-06T17:26:33Z<p>initial push in.</p>
<p><b>New page</b></p><div>==User documentation for files RingF256.C and RingF256.H==<br />
<br />
These files contain an implementation of the field with 256 elements.<br />
The fields representation is ((Z/(2))[x])/(x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1).<br />
<br />
Internally, the fields elements are stored as numbers<br />
(unsigned char's, to be specific). These numbers, interpreted as bit-streams,<br />
correspond to the univariate polynomial's sequence of coefficients. For example<br />
11 = 1* 2^3 + 0*2^2 + 1*2^1 + 1*2^0 <-> (00001011)<br />
<-> 0*x^7+ 0*x^6 + 0*x^5 + 0*x^4 + 1*x^3 + 0*x^2 + 1*x^1 + 1*x^0<br />
= x^3 + x + 1<br />
So the field element x^3 + x + 1 is internally stored as '11'.<br />
<br />
An instance of RingF256 can be created via<br />
<br />
CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF256();<br />
<br />
To see if a given CoCoA::ring R is an instance of RingF256 you can check<br />
<br />
bool b = ApCoCoa::AlgebraicCore::IsRingF256(R);<br />
<br />
Furthermore, any instance of RingF256 can be used like any other ring in CoCoA. <br />
To create an element proceed as follows:<br />
<br />
CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF256();<br />
CoCoA::RingElem e(r,11);<br />
<br />
and e represents the ring element 'x^3+x+1' or equivalently '11'. <br />
A warning: adding the element '3' to the element '2' does NOT lead to the <br />
element '5', since '3' <-> 'x+1', '2' <-> 'x' and (x+1) + (x) = 1 <-> '1'.<br />
Some more details on how elements can be stored and retrieved from this ring <br />
can be found in the example ex-RingF16.C in ApCoCoALib's example directory.<br />
<br />
==Maintainer documentation for files RingF256.C and RingF256.H==<br />
<br />
Currently, this fields uses 'semi-logarithmic' multiplication and division <br />
matrixes. This means both matrices are of size 8 times 256. <br />
<br />
To multiply a and b, we split a into its exponents (a_0, ... a_7) and <br />
XOR the elements {m_(i,b) | i=0,..7, a_i =1 } of the multiplication matrix.<br />
<br />
To divide a through b, we again split a like above and XOR the elements<br />
{d_(i,b) | i=0,..7, a_i =1 } of the division matrix.<br />
<br />
Other options would be the usage of a logarithmic matrices or two 'full'<br />
256 times 256 matrices or a double logarithmic 8 times 8 one. So we have to make a decision between XOR operations<br />
and memory usage. Which of this versions is optimal has to be checked <br />
for different problem settings. <br />
<br />
==Bugs, Shortcomings and other ideas==<br />
<br />
The current implementation does not support a lot of intractability with <br />
other rings. A set of Ringhomomorphisms could be implemented to allow a more <br />
easy switch between other representations of F_256 or to map elements in Z[x] <br />
or Z/(2)[x] into F_256.<br />
<br />
Also isomorphisms between different representations of F_256 could be <br />
implemented. Any irreducible polynomial of degree 8 in Z/(2)[x] can be used <br />
to create a representation of F_256. Based in the galois group of F_256 and the<br />
irreducible polynomial's roots in F_256 an isomorphism can be described, mapping<br />
one representation to another. This might be handy, if a special modulus is <br />
given for a computation which is not the one, used for this implementations <br />
multiplication / division matrices.<br />
<br />
==References==<br />
<br />
[[http://apcocoa.org/wiki/ApCoCoA:Representation_of_finite_fields http://apcocoa.org/wiki/ApCoCoA:Representation_of_finite_fields]] - more <br />
information on the representation of finite fields..<br />
<br />
[[http://apcocoa.org/wiki/HowTo:Construct_fields http://apcocoa.org/wiki/HowTo:Construct_fields]] - a description, how the <br />
multiplication / division matrices were constructed, including the needed <br />
source-code / tools.<br />
<br />
<br />
[[Category:ApCoCoALib_Manual]]<br />
__NOTOC__</div>Dheldt