<h4>2.1 <span class="Heading">Definition of standard finite fields</span></h4>
<p>In <a href="chapBib_mj.html#biBStdFFCyc">[Lüb23]</a> we define for each prime <span class="SimpleMath">\(p\)</span> and positive integer <span class="SimpleMath">\(n\)</span> a standardized model for the finite field with <span class="SimpleMath">\(p^n\)</span> elements. This is done by defining for each prime <span class="SimpleMath">\(r\)</span> polynomials of degree <span class="SimpleMath">\(r\)</span> which define recursively <span class="SimpleMath">\(r\)</span>-power extensions of the prime field <span class="SimpleMath">\(GF(p)\)</span> and by combining these for all <span class="SimpleMath">\(r | n\)</span> in a unique tower of extensions of finite fields where the successive degrees are non-decreasing primes.</p>
<p>Relative to this tower of prime degree extensions the resulting field comes with a natural basis over the prime field which we call the <em>tower basis</em>. This construction has the nice property that whenever <span class="SimpleMath">\(n | m\)</span> then the tower basis of the field with <span class="SimpleMath">\(p^n\)</span> elements is a subset of the tower basis of the field with <span class="SimpleMath">\(p^m\)</span> elements. (See <a href="chapBib_mj.html#biBStdFFCyc">[Lüb23]</a> for more details.)</p>
<p>Expressing elements as linear combination of the tower basis we define a bijection from the elements in the field of order <span class="SimpleMath">\(p^n\)</span> to the range <code class="code">[0..p^n-1]</code>; we call the number assigned to an element its <em>Steinitz number</em>.</p>
<p>Via this construction each element in the algebraic closure of <span class="SimpleMath">\(GF(p)\)</span> can be identified by its degree <span class="SimpleMath">\(d\)</span> over the prime field and its Steinitz number in the field with <span class="SimpleMath">\(p^d\)</span> elements (we call this a <em>Steinitz pair</em>).</p>
<p>Since arithmetic in simple algebraic extensions is more efficient than in iterated extensions we construct the fields recursively as simple extensions, and including information about the base change between the tower basis and the basis given by the powers of the generator.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardPrimeDegreePolynomial</code>( <var class="Arg">p</var>, <var class="Arg">r</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a polynomial of degree <var class="Arg">r</var></p>
<p>The arguments are a prime <var class="Arg">p</var> and a positive integer <var class="Arg">n</var>. The function <code class="func">FF</code> (or its synomym <code class="func">StandardFiniteField</code>) is one of the main functions of this package. It returns a standardized field <code class="code">F</code> of order <span class="SimpleMath">\(\textit{p}^{\textit{n}}\)</span>. It is implemented as a simple extension over the prime field <code class="code">GF(p)</code> using <code class="func">AlgebraicExtension</code> (<a href="../../../doc/ref/chap67_mj.html#X7CDA90537D2BAC8A"><span class="RefLink">Reference: AlgebraicExtension</span></a>)</p>
<p>The polynomials used for the prime degree extensions are accessible with <code class="func">StandardPrimeDegreePolynomial</code>. For arguments <var class="Arg">p, r, k</var> it returns the irreducible polynomial of degree <var class="Arg">r</var> for the <var class="Arg">k</var>-th iterated extension of degree <var class="Arg">r</var> over the prime field. The polynomial is in the variable <code class="code">x</code><em>r</em><code class="code">_</code><em>k</em> and the coefficients can contain variables <code class="code">x</code><em>r</em><code class="code">_</code><em>l</em> with <span class="SimpleMath">\(l < k\)</span>.</p>
<p>These properties identify the finite fields constructed with <code class="func">FF</code> (<a href="chap2_mj.html#X80DCBB4F84F04DDB"><span class="RefLink">2.2-1</span></a>). Prime fields constructed as <code class="code">FF(p, 1)</code> have the property <code class="func">IsStandardPrimeField</code>. They are identical with <code class="code">GF(p)</code>, but calling them via <code class="func">FF</code> (<a href="chap2_mj.html#X80DCBB4F84F04DDB"><span class="RefLink">2.2-1</span></a>) we store some additional information in these objects.</p>
<p>The fields constructed by <code class="code">FF(p,k)</code> with <code class="code">k</code> <span class="SimpleMath">\( > 1\)</span> have the property <code class="func">IsStandardFiniteField</code>. Elements <var class="Arg">x</var> in such a field are in <code class="func">IsStandardFiniteFieldElement</code>.</p>
<h4>2.3 <span class="Heading">Elements in standard finite fields</span></h4>
<p>For fields in <code class="func">IsStandardFiniteField</code> (<a href="chap2_mj.html#X7DD6C7C3867D84B8"><span class="RefLink">2.2-2</span></a>) we provide functions to map elements to their linear combination of the tower basis, to their Steinitz number and Steinitz pair, or to their representing multivariate polynomial with respect to all prime degree extensions, and vice versa.</p>
<h5>2.3-1 <span class="Heading">Maps for elements of standard finite fields</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsVector</code>( <var class="Arg">a</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a vector over prime field of <code class="code">F</code></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ElementVector</code>( <var class="Arg">F</var>, <var class="Arg">v</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an element in <code class="code">F</code></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsPolynomial</code>( <var class="Arg">a</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a polynomial in variables of the tower of <code class="code">F</code></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ElementPolynomial</code>( <var class="Arg">F</var>, <var class="Arg">pol</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an element in <code class="code">F</code></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ElementSteinitzNumber</code>( <var class="Arg">F</var>, <var class="Arg">nr</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an element in <code class="code">F</code></p>
<p>Here, <var class="Arg">F</var> is always a standard finite field (<code class="func">IsStandardFiniteField</code> (<a href="chap2_mj.html#X7DD6C7C3867D84B8"><span class="RefLink">2.2-2</span></a>)) and <var class="Arg">a</var> is an element of <var class="Arg">F</var>.</p>
<p><code class="func">AsVector</code> returns the coefficient vector of <var class="Arg">a</var> with respect to the tower basis of <var class="Arg">F</var>. And vice versa <code class="func">ElementVector</code> returns the element of <var class="Arg">F</var> with the given coefficient vector.</p>
<p>Similarly, <code class="func">AsPolynomial</code> returns the (reduced) polynomial in the indeterminates defining the tower of <var class="Arg">F</var>. Here, for each prime <span class="SimpleMath">\(r\)</span> dividing the degree of the field the polynomial defining the <span class="SimpleMath">\(k\)</span>-th extension of degree <span class="SimpleMath">\(r\)</span> over the prime field is written in the variable <code class="code">x</code><span class="SimpleMath">\(r\)</span><code class="code">_</code><span class="SimpleMath">\(k\)</span>. And <code class="func">ElementPolynomial</code> returns the element of <var class="Arg">F</var> represented by the given polynomial (which does not need to be reduced).</p>
<p>Finally, <code class="func">SteinitzNumber</code> returns the Steinitz number of <var class="Arg">a</var>. And <code class="func">ElementSteinitzNumber</code> returns the element with given Steinitz number.</p>
<h4>2.4 <span class="Heading">Embeddings of standard finite fields</span></h4>
<p>The tower basis of a standard finite field <code class="code">F</code> contains the tower basis of any subfield. This yields a construction of canonical embeddings of all subfields of <code class="code">F</code> into <code class="code">F</code>. And one can easily read off the smallest subfield containing an element in <code class="code">F</code> from its coefficient vector with respect to the tower basis. Each element of the algebraic closure of <code class="code">FF(p,1)</code> is uniquely determined by its degree <code class="code">d</code> and its Steinitz number in <code class="code">FF(p, d)</code>.</p>
<p>The argument <var class="Arg">a</var> must be an element in <code class="func">IsStandardFiniteFieldElement</code> (<a href="chap2_mj.html#X7DD6C7C3867D84B8"><span class="RefLink">2.2-2</span></a>). Then <code class="func">SteinitzPair</code> returns a pair <code class="code">[d, nr]</code> where <code class="code">d</code> is the degree of <var class="Arg">a</var> over the prime field <code class="code">FF(p, 1)</code> and <code class="code">nr</code> is the Steinitz number of <var class="Arg">a</var> considered as element of <code class="code">FF(p, d)</code>.</p>
<p>In the second variant a standard finite field <var class="Arg">K</var> is given and the Steinitz number of an element in <var class="Arg">K</var> and the result is the Steinitz pair of the corresponding element.</p>
<p>The inverse map is provided by a method for <code class="func">SteinitzNumber</code> which gets a standard finite field and a Steinitz pair.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Embedding</code>( <var class="Arg">H</var>, <var class="Arg">F</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a field homomorphism</p>
<p>Let <var class="Arg">F</var> and <var class="Arg">H</var> be standard finite fields and <var class="Arg">H</var> be isomorphic to a subfield of <var class="Arg">F</var>. This function returns the canonical embedding of <var class="Arg">H</var> into <var class="Arg">F</var>.</p>
<p>For a prime <var class="Arg">p</var>, positive integer <var class="Arg">n</var> and an integer list <var class="Arg">coeffs</var> this function returns the element in <code class="code">FF(<var class="Arg">p</var>, <var class="Arg">n</var>)</code> represented by the polynomial with coefficient list <var class="Arg">coeffs</var> modulo <var class="Arg">p</var>. Elements in standard finite fields are also printed in this way.</p>
<p>For convenience the third argument <var class="Arg">ffe</var> can be in `GF(p,n)` (see <code class="func">GF</code> (<a href="../../../doc/ref/chap59_mj.html#X8592DBB086A8A9BE"><span class="RefLink">Reference: GF for characteristic and degree</span></a>) and <code class="func">IsFFE</code> (<a href="../../../doc/ref/chap59_mj.html#X7D3DF32C84FEBD25"><span class="RefLink">Reference: IsFFE</span></a>)). This returns the image of <var class="Arg">ffe</var> under the <code class="func">StandardIsomorphismGF</code> (<a href="chap2_mj.html#X7ECCD8D27FBA9505"><spanclass="RefLink">2.4-5</span></a>) of <code class="code">FF(<var class="Arg">p</var>,<var class="Arg">n</var>)</code>.</p>
<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">x := ZZ(19,5,[1,2,3,4,5]);</span>
ZZ(19,5,[1,2,3,4,5])
<span class="GAPprompt">gap></span> <span class="GAPinput">a := PrimitiveElement(FF(19,5));</span>
ZZ(19,5,[0,1,0,0,0])
<span class="GAPprompt">gap></span> <span class="GAPinput">x = [1,2,3,4,5]*[a^0,a^1,a^2,a^3,a^4];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">One(FF(19,5)); # elements in prime field abbreviated</span>
ZZ(19,5,[1])
<span class="GAPprompt">gap></span> <span class="GAPinput">One(FF(19,5)) = ZZ(19,5,[1]);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ZZ(19,5,Z(19^5)); # zero of ConwayPolynomial(19,5)</span>
ZZ(19,5,[12,5,3,4,5])
</pre></div>
<p>Here <var class="Arg">x</var> and <var class="Arg">y</var> must be elements in standard finite fields (of the same characteristic).</p>
<p>Then <code class="func">MoveToSmallestStandardField</code> returns the element <var class="Arg">x</var> as element of the smallest possible degree extension over the prime field.</p>
<p>The arithmetic operations are even possible when <var class="Arg">x</var> and <var class="Arg">y</var> are not represented as elements in the same field. In this case the elements are first mapped to the smallest field containing both.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardIsomorphismGF</code>( <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a field isomorphism</p>
<p>The argument <var class="Arg">F</var> must be a standard finite field, say <code class="code">FF(p,n)</code> such that <strong class="pkg">GAP</strong> can generate <code class="code">GF(p,n)</code>. This function returns the field isomorphism from <code class="code">GF(p,n)</code> to <var class="Arg">F</var>, which sends <code class="code">Z(p,n)</code> to the element with Steinitz pair computed by <code class="func">SteinitzPairConwayGenerator</code> (<a href="chap4_mj.html#X784E128A811F5C91"><span class="RefLink">4.4-3</span></a>).</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.
