<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>
</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>
<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="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="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="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="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>
<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>
<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≥ 2 is a prime then GF(p) denotes the field Z}/pZ}, 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^×</span> is a cyclic group. An <span class="SimpleMath">α ∈ F</span> is called a <strong class="button">primitive element</strong> if it is a generator of <span class="SimpleMath">F^×</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>
<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 ⟨ 1 ⟨ 2 ⟨ ... ⟨ 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 ⟩ r</span>). Then we define <span class="SimpleMath">g ⟨ 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 ⟩ k</span> and <span class="SimpleMath">(-1)^r-k g_k ⟨ (-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)) ≡ 0 mod 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>
<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>
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.
