Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/guava/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 1.1.2025 mit Größe 22 kB image not shown  

SSL chap8_mj.html   Sprache: HTML

 
 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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 http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol on Conway polynomials. The prime fields: If \(p\geq 2\) is a prime then \(GF(p)\) denotes the field \({\mathbb{Z}}/p{\mathbb{Z}}\), with addition and multiplication performed mod \(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">‣ 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">‣ 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>

100%


¤ Dauer der Verarbeitung: 0.49 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.