http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoALib:RingF512&feed=atom&action=history ApCoCoALib:RingF512 - Revision history 2022-10-03T11:10:15Z Revision history for this page on the wiki MediaWiki 1.35.0 http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoALib:RingF512&diff=7368&oldid=prev Dheldt: initial push in 2008-03-06T17:28:27Z <p>initial push in</p> <p><b>New page</b></p><div>==User documentation for files RingF512.C and RingF512.H==<br /> <br /> These files contain an implementation of the field with 512 elements.<br /> The fields representation is ((Z/(2))[x])/((x^9 + x +1).<br /> <br /> Internally, the fields elements are stored as numbers<br /> (unsigned integers, 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 &lt;-&gt; (000001011)<br /> &lt;-&gt; 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::NewRingF512();<br /> <br /> To see if a given CoCoA::ring R is an instance of RingF512 you can check<br /> <br /> bool b = ApCoCoa::AlgebraicCore::IsRingF512(R);<br /> <br /> Furthermore, any instance of RingF512 can be used like any other ring in CoCoA. <br /> To create an element proceed as follows:<br /> <br /> CoCoA::ring R = ApCoCoA::AlgebraicCore::NewRingF512();<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' &lt;-&gt; 'x+1', '2' &lt;-&gt; 'x' and (x+1) + (x) = 1 &lt;-&gt; '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 RingF512.C and RingF512.H==<br /> <br /> Currently, this fields uses 'semi-logarithmic' multiplication and division <br /> matrixes. This means both matrices are of size 9 times 512. <br /> <br /> To multiply a and b, we split a into its exponents (a_0, ... a_8) and <br /> XOR the elements {m_(i,b) | i=0,..8, 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,..8, a_i =1 } of the division matrix.<br /> <br /> Other options would be the usage of a logarithmic matrices or two 'full'<br /> 512 times 512 matrices or a double logarithmic 9 times 9 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_512 or to map elements in Z[x] <br /> or Z/(2)[x] into F_512.<br /> <br /> Also isomorphisms between different representations of F_512 could be <br /> implemented. Any irreducible polynomial of degree 9 in Z/(2)[x] can be used <br /> to create a representation of F_512. Based in the galois group of F_512 and the<br /> irreducible polynomial's roots in F_512 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