| products/Sources/formale Sprachen/GAP/pkg/guava/doc/chap8_mj.html |
 |
<?xml version= "1.0" encoding= "UTF-8"?>
<! DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
< html xmlns= "http://www.w3.org/1999/xhtml" xml:lang= "en">
< head>
< script type= "text/javascript"
src= "https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< title>GAP (guava) - Chapter 8: Coding theory functions in GAP</ title>
< meta http-equiv= "content-type" content= "text/html; charset=UTF-8" />
< meta name= "generator" content= "GAPDoc2HTML" />
< link rel= "stylesheet" type= "text/css" href= "manual.css" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap8" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span>< a href= "chap0_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap7_mj.html">[Previous Chapter]</a> <a href="chap9_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap8.html">[MathJax off]</a></p>
<p><a id="X7A93308C82637F4F" name="X7A93308C82637F4F"></a></p>
<div class="ChapSects"><a href="chap8_mj.html#X7A93308C82637F4F">8 <span class="Heading">Coding theory functions in GAP</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8_mj.html#X80F192497C008691">8.1 <span class="Heading">
Distance functions
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8_mj.html#X82E5987E81487D18">8.1-1 AClosestVectorCombinationsMatFFEVecFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8_mj.html#X870DE258833C5AA0">8.1-2 AClosestVectorComb..MatFFEVecFFECoords</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8_mj.html#X85135CEB86E61D49">8.1-3 DistancesDistributionMatFFEVecFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8_mj.html#X7F2F630984A9D3D6">8.1-4 DistancesDistributionVecFFEsVecFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8_mj.html#X7C9F4D657F9BA5A1">8.1-5 WeightVecFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8_mj.html#X85AA5C6587559C1C">8.1-6 DistanceVecFFE</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8_mj.html#X87C3D1B984960984">8.2 <span class="Heading">
Other functions
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8_mj.html#X7C2425A786F09054">8.2-1 ConwayPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8_mj.html#X7ECC593583E68A6C">8.2-2 RandomPrimitivePolynomial</a></span>
</div></div>
</div>
<h3>8 <span class="Heading">Coding theory functions in GAP</span></h3>
<p>This chapter will recall from the GAP4.4.5 manual some of the GAP coding theory and finite field functions useful for coding theory. Some of these functions are partially written in C for speed. The main functions are</p>
<ul>
<li><p><code class="code">AClosestVectorCombinationsMatFFEVecFFE</code>,</p>
</li>
<li><p><code class="code">AClosestVectorCombinationsMatFFEVecFFECoords</code>,</p>
</li>
<li><p><code class="code">CosetLeadersMatFFE</code>,</p>
</li>
<li><p><code class="code">DistancesDistributionMatFFEVecFFE</code>,</p>
</li>
<li><p><code class="code">DistancesDistributionVecFFEsVecFFE</code>,</p>
</li>
<li><p><code class="code">DistanceVecFFE</code> and <code class="code">WeightVecFFE</code>,</p>
</li>
<li><p><code class="code">ConwayPolynomial</code> and <code class="code">IsCheapConwayPolynomial</code>,</p>
</li>
<li><p><code class="code">IsPrimitivePolynomial</code>, and <code class="code">RandomPrimitivePolynomial</code>.</p>
</li>
</ul>
<p>However, the GAP command <code class="code">PrimitivePolynomial</code> returns an integer primitive polynomial not the finite field kind.</p>
<p><a id="X80F192497C008691" name="X80F192497C008691"></a></p>
<h4>8.1 <span class="Heading">
Distance functions
</span></h4>
<p><a id="X82E5987E81487D18" name="X82E5987E81487D18"></a></p>
<h5>8.1-1 AClosestVectorCombinationsMatFFEVecFFE</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AClosestVectorCombinationsMatFFEVecFFE</code>( <var class="Arg">mat</var>, <var class="Arg">F</var>, <var class="Arg">vec</var>, <var class="Arg">r</var>, <var class="Arg">st</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command runs through the <var class="Arg">F</var>-linear combinations of the vectors in the rows of the matrix <var class="Arg">mat</var> that can be written as linear combinations of exactly <var class="Arg">r</var> rows (that is without using zero as a coefficient) and returns a vector from these that is closest to the vector <var class="Arg">vec</var>. The length of the rows of <var class="Arg">mat</var> and the length of <var class="Arg">vec</var> must be equal, and all elements must lie in <var class="Arg">F</var>. The rows of <var class="Arg">mat</var> must be linearly independent. If it finds a vector of distance at most <var class="Arg">st</var>, which must be a nonnegative integer, then it stops immediately and returns this vector.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F:=GF(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:= Indeterminate( F, "x" );; pol:= x^2+1;</span>
x^2+Z(3)^0
<span class="GAPprompt">gap></span> <span class="GAPinput">C := GeneratorPolCode(pol,8,F);</span>
a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)
<span class="GAPprompt">gap></span> <span class="GAPinput">v:=Codeword("12101111");</span>
[ 1 2 1 0 1 1 1 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">v:=VectorCodeword(v);</span>
[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">G:=GeneratorMat(C);</span>
[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
[ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
[ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],
[ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],
[ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],
[ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AClosestVectorCombinationsMatFFEVecFFE(G,F,v,1,1);</span>
[ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ]
</pre></div>
<p><a id="X870DE258833C5AA0" name="X870DE258833C5AA0"></a></p>
<h5>8.1-2 AClosestVectorComb..MatFFEVecFFECoords</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AClosestVectorComb..MatFFEVecFFECoords</code>( <var class="Arg">mat</var>, <var class="Arg">F</var>, <var class="Arg">vec</var>, <var class="Arg">r</var>, <var class="Arg">st</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">AClosestVectorCombinationsMatFFEVecFFECoords</code> returns a two element list containing (a) the same closest vector as in <code class="code">AClosestVectorCombinationsMatFFEVecFFE</code>, and (b) a vector <var class="Arg">v</var> with exactly <var class="Arg">r</var> non-zero entries, such that <span class="SimpleMath">\(v*mat\)</span> is the closest vector.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F:=GF(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:= Indeterminate( F, "x" );; pol:= x^2+1;</span>
x^2+Z(3)^0
<span class="GAPprompt">gap></span> <span class="GAPinput">C := GeneratorPolCode(pol,8,F);</span>
a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)
<span class="GAPprompt">gap></span> <span class="GAPinput">v:=Codeword("12101111"); v:=VectorCodeword(v);;</span>
[ 1 2 1 0 1 1 1 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">G:=GeneratorMat(C);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AClosestVectorCombinationsMatFFEVecFFECoords(G,F,v,1,1);</span>
[ [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ],
[ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ]
</pre></div>
<p><a id="X85135CEB86E61D49" name="X85135CEB86E61D49"></a></p>
<h5>8.1-3 DistancesDistributionMatFFEVecFFE</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DistancesDistributionMatFFEVecFFE</code>( <var class="Arg">mat</var>, <var class="Arg">f</var>, <var class="Arg">vec</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">DistancesDistributionMatFFEVecFFE</code> returns the distances distribution of the vector <var class="Arg">vec</var> to the vectors in the vector space generated by the rows of the matrix <var class="Arg">mat</var> over the finite field <var class="Arg">f</var>. All vectors must have the same length, and all elements must lie in a common field. The distances distribution is a list <span class="SimpleMath">\(d\)</span> of length <span class="SimpleMath">\(Length(vec)+1\)</span>, such that the value <span class="SimpleMath">\(d[i]\)</span> is the number of vectors in vecs that have distance <span class="SimpleMath">\(i+1\)</span> to <var class="Arg">vec</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">vecs:=[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DistancesDistributionMatFFEVecFFE(vecs,GF(3),v);</span>
[ 0, 4, 6, 60, 109, 216, 192, 112, 30 ]
</pre></div>
<p><a id="X7F2F630984A9D3D6" name="X7F2F630984A9D3D6"></a></p>
<h5>8.1-4 DistancesDistributionVecFFEsVecFFE</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DistancesDistributionVecFFEsVecFFE</code>( <var class="Arg">vecs</var>, <var class="Arg">vec</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">DistancesDistributionVecFFEsVecFFE</code> returns the distances distribution of the vector <var class="Arg">vec</var> to the vectors in the list <var class="Arg">vecs</var>. All vectors must have the same length, and all elements must lie in a common field. The distances distribution is a list <span class="SimpleMath">\(d\)</span> of length <span class="SimpleMath">\(Length(vec)+1\)</span>, such that the value <span class="SimpleMath">\(d[i]\)</span> is the number of vectors in <var class="Arg">vecs</var> that have distance <span class="SimpleMath">\(i+1\)</span> to <var class="Arg">vec</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">vecs:=[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DistancesDistributionVecFFEsVecFFE(vecs,v);</span>
[ 0, 0, 0, 0, 0, 4, 0, 1, 1 ]
</pre></div>
<p><a id="X7C9F4D657F9BA5A1" name="X7C9F4D657F9BA5A1"></a></p>
<h5>8.1-5 WeightVecFFE</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; WeightVecFFE</code>( <var class="Arg">vec</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">WeightVecFFE</code> returns the weight of the finite field vector <var class="Arg">vec</var>, i.e. the number of nonzero entries.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">WeightVecFFE(v);</span>
7
</pre></div>
<p><a id="X85AA5C6587559C1C" name="X85AA5C6587559C1C"></a></p>
<h5>8.1-6 DistanceVecFFE</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DistanceVecFFE</code>( <var class="Arg">vec1</var>, <var class="Arg">vec2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The <em>Hamming metric</em> on <span class="SimpleMath">\(GF(q)^n\)</span> is the function</p>
<p class="center">\[
dist((v_1,...,v_n),(w_1,...,w_n))
=|\{i\in [1..n]\ |\ v_i\not= w_i\}|.
\]</p>
<p>This is also called the (Hamming) distance between <span class="SimpleMath">\(v=(v_1,...,v_n)\)</span> and <span class="SimpleMath">\(w=(w_1,...,w_n)\)</span>. <code class="code">DistanceVecFFE</code> returns the distance between the two vectors <var class="Arg">vec1</var> and <var class="Arg">vec2</var>, which must have the same length and whose elements must lie in a common field. The distance is the number of places where <var class="Arg">vec1</var> and <var class="Arg">vec2</var> differ.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">v1:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">v2:=[ Z(3), Z(3)^0, Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DistanceVecFFE(v1,v2);</span>
2
</pre></div>
<p><a id="X87C3D1B984960984" name="X87C3D1B984960984"></a></p>
<h4>8.2 <span class="Heading">
Other functions
</span></h4>
<p>We basically repeat, with minor variation, the material in the GAP manual or from Frank Luebeck's website <span class="URL"><a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol">http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol</a></span> on Conway polynomials. The <strong class="button">prime fields</strong>: If <span class="SimpleMath">\(p\geq 2\)</span> is a prime then <span class="SimpleMath">\(GF(p)\)</span> denotes the field <span class="SimpleMath">\({\mathbb{Z}}/p{\mathbb{Z}}\)</span>, with addition and multiplication performed mod <span class="SimpleMath">\(p\)</span>.</p>
<p>The <strong class="button">prime power fields</strong>: Suppose <span class="SimpleMath">\(q=p^r\)</span> is a prime power, <span class="SimpleMath">\(r>1\)</span>, and put <span class="SimpleMath">\(F=GF(p)\)</span>. Let <span class="SimpleMath">\(F[x]\)</span> denote the ring of all polynomials over <span class="SimpleMath">\(F\)</span> and let <span class="SimpleMath">\(f(x)\)</span> denote a monic irreducible polynomial in <span class="SimpleMath">\(F[x]\)</span> of degree <span class="SimpleMath">\(r\)</span>. The quotient <span class="SimpleMath">\(E = F[x]/(f(x))= F[x]/f(x)F[x]\)</span> is a field with <span class="SimpleMath">\(q\)</span> elements. If <span class="SimpleMath">\(f(x)\)</span> and <span class="SimpleMath">\(E\)</span> are related in this way, we say that <span class="SimpleMath">\(f(x)\)</span> is the <strong class="button">defining polynomial</strong> of <span class="SimpleMath">\(E\)</span>. Any defining polynomial factors completely into distinct linear factors over the field it defines.</p>
<p>For any finite field <span class="SimpleMath">\(F\)</span>, the multiplicative group of non-zero elements <span class="SimpleMath">\(F^\times\)</span> is a cyclic group. An <span class="SimpleMath">\(\alpha \in F\)</span> is called a <strong class="button">primitive element</strong> if it is a generator of <span class="SimpleMath">\(F^\times\)</span>. A defining polynomial <span class="SimpleMath">\(f(x)\)</span> of <span class="SimpleMath">\(F\)</span> is said to be <strong class="button">primitive</strong> if it has a root in <span class="SimpleMath">\(F\)</span> which is a primitive element.</p>
<p><a id="X7C2425A786F09054" name="X7C2425A786F09054"></a></p>
<h5>8.2-1 ConwayPolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ConwayPolynomial</code>( <var class="Arg">p</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>A standard notation for the elements of <span class="SimpleMath">\(GF(p)\)</span> is given via the representatives <span class="SimpleMath">\(0, ..., p-1\)</span> of the cosets modulo <span class="SimpleMath">\(p\)</span>. We order these elements by <span class="SimpleMath">\(0 \ \ \langle\ \ 1 \ \ \langle\ \ 2 \ \ \langle\ \ ... \ \ \langle\ \ p-1\)</span>. We introduce an ordering of the polynomials of degree <span class="SimpleMath">\(r\)</span> over <span class="SimpleMath">\(GF(p)\)</span>. Let <span class="SimpleMath">\(g(x) = g_rx^r + ... + g_0\)</span> and <span class="SimpleMath">\(h(x) = h_rx^r + ... + h_0\)</span> (by convention, <span class="SimpleMath">\(g_i=h_i=0\)</span> for <span class="SimpleMath">\(i\ \ \rangle\ \ r\)</span>). Then we define <span class="SimpleMath">\(g \ \ \langle\ \ h\)</span> if and only if there is an index <span class="SimpleMath">\(k\)</span> with <span class="SimpleMath">\(g_i = h_i\)</span> for <span class="SimpleMath">\(i \ \ \rangle\ \ k\)</span> and <span class="SimpleMath">\((-1)^{r-k} g_k \ \ \langle\ \ (-1)^{r-k} h_k\)</span>.</p>
<p>The <strong class="button">Conway polynomial</strong> <span class="SimpleMath">\(f_{p,r}(x)\)</span> for <span class="SimpleMath">\(GF(p^r)\)</span> is the smallest polynomial of degree <span class="SimpleMath">\(r\)</span> with respect to this ordering such that:</p>
<ul>
<li><p><span class="SimpleMath">\(f_{p,r}(x)\)</span> is monic,</p>
</li>
<li><p><span class="SimpleMath">\(f_{p,r}(x)\)</span> is primitive, that is, any zero is a generator of the (cyclic) multiplicative group of <span class="SimpleMath">\(GF(p^r)\)</span>,</p>
</li>
<li><p>for each proper divisor <span class="SimpleMath">\(m\)</span> of <span class="SimpleMath">\(r\)</span> we have that <span class="SimpleMath">\(f_{p,m}(x^{(p^r-1) / (p^m-1)}) \equiv 0 \pmod{f_{p,r}(x)}\)</span>; that is, the <span class="SimpleMath">\((p^r-1) / (p^m-1)\)</span>-th power of a zero of <span class="SimpleMath">\(f_{p,r}(x)\)</span> is a zero of <span class="SimpleMath">\(f_{p,m}(x)\)</span>.</p>
</li>
</ul>
<p><code class="code">ConwayPolynomial(p,n)</code> returns the polynomial <span class="SimpleMath">\(f_{p,r}(x)\)</span> defined above.</p>
<p><code class="code">IsCheapConwayPolynomial(p,n)</code> returns true if <code class="code">ConwayPolynomial( p, n )</code> will give a result in reasonable time. This is either the case when this polynomial is pre-computed, or if <span class="SimpleMath">\(n,p\)</span> are not too big.</p>
<p><a id="X7ECC593583E68A6C" name="X7ECC593583E68A6C"></a></p>
<h5>8.2-2 RandomPrimitivePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RandomPrimitivePolynomial</code>( <var class="Arg">F</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For a finite field <var class="Arg">F</var> and a positive integer <var class="Arg">n</var> this function returns a primitive polynomial of degree <var class="Arg">n</var> over <var class="Arg">F</var>, that is a zero of this polynomial has maximal multiplicative order <span class="SimpleMath">\(|F|^n-1\)</span>.</p>
<p><code class="code">IsPrimitivePolynomial(f)</code> can be used to check if a univariate polynomial <var class="Arg">f</var> is primitive or not.</p>
<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap7_mj.html">[Previous Chapter]</a> <a href="chap9_mj.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
¤ Dauer der Verarbeitung: 0.17 Sekunden
¤
*© Formatika GbR, Deutschland
|
|
