Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/standardff/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 13.8.2023 mit Größe 43 kB image not shown  

Quelle  chap4.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/standardff/doc/chap4.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>
<title>GAP (StandardFF) - Chapter 4: Utilities from the StandardFF package</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="chap4"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chapBib.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap4_mj.html">[MathJax on]</a></p>
<p><a id="X7B7EC1DC7BF3A7BD" name="X7B7EC1DC7BF3A7BD"></a></p>
<div class="ChapSects"><a href="chap4.html#X7B7EC1DC7BF3A7BD">4 <span class="Heading">Utilities from the <strong class="pkg">StandardFF</strong> package</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7BFCD0EA853203E8">4.1 <span class="Heading">A simple bijection on a range</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X85113F358019E11C">4.1-1 StandardAffineShift</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X845FFCBC7CE095A6">4.2 <span class="Heading">Finding linear combinations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7F1ABC6E83E257A3">4.2-1 FindLinearCombination</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X876B131786C80F86">4.3 <span class="Heading">Irreducibility over finite fields</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7F7C09C3860AF01D">4.3-1 IsIrreducibleCoeffList</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X86D4E7A6830D51D3">4.4 <span class="Heading">Connection to Conway polynomials</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7E781D7B7CB1DFF4">4.4-1 FindConjugateZeroes</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7C00A74780A75A10">4.4-2 ZeroesConway</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X784E128A811F5C91">4.4-3 SteinitzPairConwayGenerator</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X846AF3D08713D57A">4.5 <span class="Heading">Discrete logarithms</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X84A138947E8C49A8">4.5-1 DLog</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X83936E9986D475BA">4.6 <span class="Heading">Minimal polynomials of sequences</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7E978CBD81D69FA2">4.6-1 InvModCoeffs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7CE85678790D8967">4.6-2 BerlekampMassey</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7BBC9E097F02B26E">4.6-3 MinimalPolynomialByBerlekampMassey</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7C69EBE885DA1B15">4.7 <span class="Heading">Brauer characters with respect to different lifts</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X86408E6883916C5D">4.7-1 StandardValuesBrauerCharacter</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X814BE20A81F82969">4.7-2 <span class="Heading">Frobenius character values</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X78ED090878CEE6AA">4.8 <span class="Heading">Known factorizations of multiplicative group orders</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7BAF533D86DAD073">4.8-1 CANFACT</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7D85D01D7F846000">4.9 <span class="Heading">Some loops for  <strong class="pkg">StandardFF</strong></span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X788898E979B9E9D9">4.9-1 <span class="Heading">Computing all fields in various ranges</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7EA72E8A78A4ADE2">4.10 <span class="Heading">Undocumented features</span></a>
</span>
</div>
</div>

<h3>4 <span class="Heading">Utilities from the <strong class="pkg">StandardFF</strong> package</span></h3>

<p><a id="X7BFCD0EA853203E8" name="X7BFCD0EA853203E8"></a></p>

<h4>4.1 <span class="Heading">A simple bijection on a range</span></h4>

<p><a id="X85113F358019E11C" name="X85113F358019E11C"></a></p>

<h5>4.1-1 StandardAffineShift</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardAffineShift</code>( <var class="Arg">q</var>, <var class="Arg">i</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an integer in range <code class="code">[0..q-1]</code></p>

<p>This function returns <span class="SimpleMath">(m <var class="Arg">i</var> + a) mod <var class="Arg">q</var></span>, where <span class="SimpleMath">m</span> is the largest integer prime to <var class="Arg">q</var> and <span class="SimpleMath">≤ 4 <var class="Arg">q</var> / 5</span>, and a is the largest integer <span class="SimpleMath">≤ 2 <var class="Arg">q</var> / 3</span>.</p>

<p>For fixed <span class="SimpleMath">q</span> this function provides a bijection on the range <code class="code">[0..q-1]</code>.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">List([0..10], i-> StandardAffineShift(11, i));</span>
[ 7, 4, 1, 9, 6, 3, 0, 8, 5, 2, 10 ]
</pre></div>

<p><a id="X845FFCBC7CE095A6" name="X845FFCBC7CE095A6"></a></p>

<h4>4.2 <span class="Heading">Finding linear combinations</span></h4>

<p><a id="X7F1ABC6E83E257A3" name="X7F1ABC6E83E257A3"></a></p>

<h5>4.2-1 FindLinearCombination</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FindLinearCombination</code>( <var class="Arg">v</var>, <var class="Arg">start</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a pair <code class="code">[serec, lk]</code> of a record and vector or <code class="keyw">fail</code></p>

<p>Repeated calls of this function build up a semiechelon basis from the given arguments <var class="Arg">v</var> which must be row vectors. To initialize a computation the function is called with a start vector <var class="Arg">v</var> and <code class="keyw">false</code> as second argument. The return value is a pair <code class="code">[serec, lk]</code> where <code class="code">serec</code> is a record which collects data from the previous calls of the function and <code class="code">lk</code> is a row vector which expresses <var class="Arg">v</var> as linear combination of the vectors from previous calls, or <code class="keyw">fail</code> if there is no such linear combination. In the latter case the data in the record is extended with the linearly independent vector <code class="code">v</code>.</p>

<p>In the following example we show how to compute a divisor of the minimal polynomial of a matrix.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">mat := Product(GeneratorsOfGroup(Sp(30,5)));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Indeterminate(GF(5), "x");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">v := (mat^0)[1];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := FindLinearCombination(v, false);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">repeat</span>
<span class="GAPprompt">></span> <span class="GAPinput">  v := v*mat;</span>
<span class="GAPprompt">></span> <span class="GAPinput">  l := FindLinearCombination(v, b[1]);</span>
<span class="GAPprompt">></span> <span class="GAPinput">until IsList(l[2]);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mp := Value(UnivariatePolynomial(GF(5),</span>
<span class="GAPprompt">></span> <span class="GAPinput">        Concatenation(-l[2], [One(GF(5))])), x);</span>
x^30+Z(5)^3*x^29+Z(5)^3*x+Z(5)^0
<span class="GAPprompt">gap></span> <span class="GAPinput"># equal to minimal polynomial because of degree</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mp = Value(MinimalPolynomial(GF(5), mat), x);</span>
true
</pre></div>

<p><a id="X876B131786C80F86" name="X876B131786C80F86"></a></p>

<h4>4.3 <span class="Heading">Irreducibility over finite fields</span></h4>

<p><a id="X7F7C09C3860AF01D" name="X7F7C09C3860AF01D"></a></p>

<h5>4.3-1 IsIrreducibleCoeffList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsIrreducibleCoeffList</code>( <var class="Arg">coeffs</var>, <var class="Arg">q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code></p>

<p>The argument <var class="Arg">coeffs</var> must be a list of elements in a finite field with <var class="Arg">q</var> elements (or some subfield of it).</p>

<p>The function checks if the univariate polynomial <span class="SimpleMath">f</span> with coefficient list <var class="Arg">coeffs</var> (ending with the leading coefficient) is irreducible over the field with <var class="Arg">q</var> elements.</p>

<p>The algorithm computes the greatest common divisor of <span class="SimpleMath">f</span> with <span class="SimpleMath">X^{q^i} - X</span> for <span class="SimpleMath">i = 1, 2, ...</span> up to half of the degree of <span class="SimpleMath">f</span>.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">cs := Z(3)^0 * ConwayPol(3,8);</span>
[ Z(3), Z(3), Z(3), 0*Z(3), Z(3)^0, Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIrreducibleCoeffList(cs, 3);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FF(17,4);; x := PrimitiveElement(F);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cs := [x, x+x^0, 0*x, x^0];</span>
[ ZZ(17,4,[0,1,0,0]), ZZ(17,4,[1,1,0,0]), ZZ(17,4,[0]), ZZ(17,4,[1]) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">while not IsIrreducibleCoeffList(cs, 17^4) do</span>
<span class="GAPprompt">></span> <span class="GAPinput">   cs[1] := cs[1] + One(F);</span>
<span class="GAPprompt">></span> <span class="GAPinput">od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cs;</span>
[ ZZ(17,4,[8,1,0,0]), ZZ(17,4,[1,1,0,0]), ZZ(17,4,[0]), ZZ(17,4,[1]) ]
</pre></div>

<p><a id="X86D4E7A6830D51D3" name="X86D4E7A6830D51D3"></a></p>

<h4>4.4 <span class="Heading">Connection to Conway polynomials</span></h4>

<p><a id="X7E781D7B7CB1DFF4" name="X7E781D7B7CB1DFF4"></a></p>

<h5>4.4-1 FindConjugateZeroes</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FindConjugateZeroes</code>( <var class="Arg">K</var>, <var class="Arg">cpol</var>, <var class="Arg">qq</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of field elements</p>

<p>The arguments must be a finite field <var class="Arg">K</var>, a polynomial <var class="Arg">cpol</var> over <var class="Arg">K</var> (or its coefficient list) and the order <var class="Arg">qq</var> of a subfield of <var class="Arg">K</var>. The polynomial must have coeffcients in the subfield with <var class="Arg">qq</var> elements, must be irreducible over this subfield and split into linear factors over <var class="Arg">K</var>. The function <code class="func">FindConjugateZeroes</code> returns the list of zeroes of <var class="Arg">cpol</var> in <var class="Arg">K</var>.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">K := GF(67,18);</span>
GF(67^18)
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FF(67,18);</span>
FF(67, 18)
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := DefiningPolynomial(K);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := DefiningPolynomial(F);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">lK := FindConjugateZeroes(K, p2, 67);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">lF := FindConjugateZeroes(F, p1, 67);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Minimum(List(lF, SteinitzNumber));</span>
12274789318154414216760893584069
</pre></div>

<p><a id="X7C00A74780A75A10" name="X7C00A74780A75A10"></a></p>

<h5>4.4-2 ZeroesConway</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ZeroesConway</code>( <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of field elements</p>

<p>Here, <var class="Arg">F</var> must be a standard finite field, say of degree <span class="SimpleMath">n</span> over the prime field with <span class="SimpleMath">p</span> elements. This function returns the same as <code class="code">FindConjugateZeroes(F, One(F)*ConwayPol(p, n), p)</code> (using a specific implementation).</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">F := FF(23,29);</span>
FF(23, 29)
<span class="GAPprompt">gap></span> <span class="GAPinput">l := Set(FindConjugateZeroes(F, One(F)*ConwayPol(23,29), 23));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">l = Set(ZeroesConway(F));</span>
true
</pre></div>

<p><a id="X784E128A811F5C91" name="X784E128A811F5C91"></a></p>

<h5>4.4-3 SteinitzPairConwayGenerator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SteinitzPairConwayGenerator</code>( <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a pair of integers</p>

<p>For a standard finite field <var class="Arg">F</var> of order <span class="SimpleMath">q</span> for which a Conway polynomial (see <code class="func">ConwayPolynomial</code> (<a href="../../../doc/ref/chap59.html#X7C2425A786F09054"><span class="RefLink">Reference: ConwayPolynomial</span></a>)) is known this function returns the <code class="func">SteinitzPair</code> (<a href="chap2.html#X85BC2EF17DA2E707"><span class="RefLink">2.4-1</span></a>) for the element of <var class="Arg">F</var> corresponding to <code class="code">Z(q)</code> (which is by definition the zero of the Conway polynomial in <var class="Arg">F</var> with the smallest Steinitz number which is compatible with the choice in all proper subfields).</p>

<p>This is used to construct the <code class="func">StandardIsomorphismGF</code> (<a href="chap2.html#X7ECCD8D27FBA9505"><span class="RefLink">2.4-5</span></a>) for <var class="Arg">F</var>.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">F := FF(23,18);</span>
FF(23, 18)
<span class="GAPprompt">gap></span> <span class="GAPinput">st := SteinitzPairConwayGenerator(F);</span>
[ 18, 1362020736983803830549380 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">st9 := SteinitzPairConwayGenerator(FF(23,9));</span>
[ 9, 206098743447 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">st6 := SteinitzPairConwayGenerator(FF(23,6));</span>
[ 6, 45400540 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">z  := ElementSteinitzNumber(F, st[2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">z9 := ElementSteinitzNumber(F, SteinitzNumber(F, st9));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">z6 := ElementSteinitzNumber(F, SteinitzNumber(F, st6));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">e9 := (Size(F)-1)/(23^9-1);</span>
1801152661464
<span class="GAPprompt">gap></span> <span class="GAPinput">e6 := (Size(F)-1)/(23^6-1);</span>
21914624580056211
<span class="GAPprompt">gap></span> <span class="GAPinput">z9 = z^e9;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">z6 = z^e6;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">l := Filtered(ZeroesConway(F), x-> x^e9 = z9 and x^e6 = z6);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(l, SteinitzNumber);</span>
[ 1362020736983803830549380 ]
</pre></div>

<p><a id="X846AF3D08713D57A" name="X846AF3D08713D57A"></a></p>

<h4>4.5 <span class="Heading">Discrete logarithms</span></h4>

<p><a id="X84A138947E8C49A8" name="X84A138947E8C49A8"></a></p>

<h5>4.5-1 DLog</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DLog</code>( <var class="Arg">base</var>, <var class="Arg">x</var>[, <var class="Arg">m</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an integer</p>

<p>The argument <var class="Arg">base</var> must be a multiplicative element and <var class="Arg">x</var> must lie in the cyclic group generated by <var class="Arg">base</var>. The third argument <var class="Arg">m</var> must be the order of <var class="Arg">base</var> or its factorization. If <var class="Arg">m</var> is not given, it is computed first. This function returns the discrete logarithm, that is an integer <span class="SimpleMath">e</span> such that <var class="Arg">base</var><span class="SimpleMath">^e =</span> <var class="Arg">x</var>.</p>

<p>If <var class="Arg">m</var> is prime then Shanks' algorithm is used (which needs O(sqrtm) space and time). Otherwise let m = r l and e = a + b r with 0 ≤ a < r. Then a = DLog(base^l, x^l, r) and b = DLog(base^r, x/base^a, l).



<p>This function is used for a method of <code class="func">LogFFE</code> (<a href="../../../doc/ref/chap59.html#X7B049A3478B369E4"><span class="RefLink">Reference: LogFFE</span></a>).</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">F := FF(67, 12);</span>
FF(67, 12)
<span class="GAPprompt">gap></span> <span class="GAPinput">st := SteinitzPairConwayGenerator(F);</span>
[ 12, 5118698034368952035290 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">z := ElementSteinitzNumber(F, st[2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := StandardPrimitiveRoot(F);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DLog(z, x, Size(F)-1);</span>
231901568073107448223
<span class="GAPprompt">gap></span> <span class="GAPinput">K := GF(67,12);</span>
GF(67^12)
<span class="GAPprompt">gap></span> <span class="GAPinput">zz := Z(67^12);</span>
z
<span class="GAPprompt">gap></span> <span class="GAPinput">LogFFE(zz^2+1, zz);</span>
1667375214152688471247
</pre></div>

<p><a id="X83936E9986D475BA" name="X83936E9986D475BA"></a></p>

<h4>4.6 <span class="Heading">Minimal polynomials of sequences</span></h4>

<p><a id="X7E978CBD81D69FA2" name="X7E978CBD81D69FA2"></a></p>

<h5>4.6-1 InvModCoeffs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InvModCoeffs</code>( <var class="Arg">fcoeffs</var>, <var class="Arg">gcoeffs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a list of <code class="keyw">fail</code></p>

<p>The arguments <var class="Arg">fcoeffs</var> and <var class="Arg">gcoeffs</var> are coeffient lists of two polynomials <span class="SimpleMath">f</span> and <span class="SimpleMath">g</span>. This operation returns the coefficient list of the inverse <span class="SimpleMath">f^-1</span> modulo <span class="SimpleMath">g</span>, if <span class="SimpleMath">f</span> and <span class="SimpleMath">g</span> are coprime, and <code class="keyw">fail</code> otherwise.</p>

<p>The default method computes the inverse by the extended Euclidean algorithm.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">f := Z(13)^0*[ 1, 10, 1, 11, 0, 1 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Z(13)^0*[ 5, 12, 5, 12, 2, 0, 2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">InvModCoeffs(f, g);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">GcdCoeffs(f, g);</span>
[ Z(13)^0, 0*Z(13), Z(13)^0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f[1]:=f[1]+1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">finv := InvModCoeffs(f, g);</span>
[ Z(13)^9, Z(13)^10, Z(13)^10, Z(13)^8, Z(13)^5, Z(13)^6 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">pr := ProductCoeffs(finv, f);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ReduceCoeffs(pr, g);; ShrinkRowVector(pr);; pr;</span>
[ Z(13)^0 ]
</pre></div>

<p><a id="X7CE85678790D8967" name="X7CE85678790D8967"></a></p>

<h5>4.6-2 BerlekampMassey</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BerlekampMassey</code>( <var class="Arg">u</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of field elements</p>

<p>The argument <var class="Arg">u</var> is a list of elements in a field <span class="SimpleMath">F</span>. This function implements the Berlekamp-Massey algorithm which returns the shortest sequence <span class="SimpleMath">c</span> of elements in <span class="SimpleMath">F</span> such that for each <span class="SimpleMath">i > l</span>, the length of <span class="SimpleMath">c</span>, we have <span class="SimpleMath">u[i] = ∑_{j=1}^l <var class="Arg">u</var>[i-j] c[j]</span>.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">x := Indeterminate(GF(23), "x");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := x^5 + Z(23)^16*x + Z(23)^12;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">u := List([1..50], i-> Value(x^i mod f, 0));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">c := BerlekampMassey(u);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll([6..50], i-> u[i] = Sum([1..5], j-> u[i-j]*c[j]));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">-c;</span>
[ 0*Z(23), 0*Z(23), 0*Z(23), Z(23)^16, Z(23)^12 ]
</pre></div>

<p><a id="X7BBC9E097F02B26E" name="X7BBC9E097F02B26E"></a></p>

<h5>4.6-3 MinimalPolynomialByBerlekampMassey</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalPolynomialByBerlekampMassey</code>( <var class="Arg">x</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalPolynomialByBerlekampMasseyShoup</code>( <var class="Arg">x</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the minimal polynomial of <var class="Arg">x</var></p>

<p>Here <span class="SimpleMath">x</span> must be an element of an algebraic extension field <span class="SimpleMath">F/K</span>. (<span class="SimpleMath">K</span> must be the <code class="func">LeftActingDomain</code> (<a href="../../../doc/ref/chap57.html#X86F070E0807DC34E"><span class="RefLink">Reference: LeftActingDomain</span></a>) of <span class="SimpleMath">F</span>). This function computes the minimal polynomial of <var class="Arg">x</var> over <span class="SimpleMath">K</span> by applying the Berlekamp-Massey algorithm to the list of traces of <span class="SimpleMath"><var class="Arg">x</var>^i</span>.</p>

<p>The second variant uses the algorithm by Shoup in <a href="chapBib.html#biBShoupMiPo">[Sho99]</a>.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">x := Indeterminate(GF(23), "x");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := x^5 + Z(23)^16*x + Z(23)^12;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := AlgebraicExtension(GF(23), f);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mp := MinimalPolynomialByBerlekampMassey(PrimitiveElement(F));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Value(mp, x) = f;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">mp = MinimalPolynomialByBerlekampMasseyShoup(PrimitiveElement(F));</span>
true
</pre></div>

<p><a id="X7C69EBE885DA1B15" name="X7C69EBE885DA1B15"></a></p>

<h4>4.7 <span class="Heading">Brauer characters with respect to different lifts</span></h4>

<p>Let <span class="SimpleMath">G</span> be a finite group, <span class="SimpleMath">g ∈ G</span>, and <span class="SimpleMath">ρ: G -> GL(d,p^n)</span>be a representation over a finite field. The Brauer character value <span class="SimpleMath">χ(g)</span> of <span class="SimpleMath">ρ</span> at <span class="SimpleMath">g</span> is defined as the sum of the eigenvalues of <span class="SimpleMath">ρ(g)</span> in the algebraic closure of <span class="SimpleMath">F_p</span> lifted to complex roots of unity.</p>

<p>The lift used by <code class="func">BrauerCharacterValue</code> (<a href="../../../doc/ref/chap72.html#X8304B68E84511685"><span class="RefLink">Reference: BrauerCharacterValue</span></a>) and in the computation of many Brauer character tables (available through the <strong class="pkg">CTblLib</strong> package) is defined by Conway polynomials (see <code class="func">ConwayPolynomial</code> (<a href="../../../doc/ref/chap59.html#X7C2425A786F09054"><span class="RefLink">Reference: ConwayPolynomial</span></a>)): They define the primitive root <code class="code">Z(q)</code> in <code class="code">GF(q)</code> which is mapped to <span class="SimpleMath">exp(2 π i / (q-1))</span> (that is <code class="code">E(q-1)</code> in <strong class="pkg">GAP</strong>).</p>

<p>Another lift is defined by the function <code class="func">StandardCyclicGenerator</code> (<a href="chap3.html#X79D3165F833F28DA"><span class="RefLink">3.1-1</span></a>) provided by this package. Here, <code class="code">StandardCyclicGenerator(F, m)</code> is mapped to <span class="SimpleMath">exp(2 π i / m)</span> (that is <code class="code">E(m)</code> in <strong class="pkg">GAP</strong>).</p>

<p>The following function translates between these two lifts.</p>

<p><a id="X86408E6883916C5D" name="X86408E6883916C5D"></a></p>

<h5>4.7-1 StandardValuesBrauerCharacter</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardValuesBrauerCharacter</code>( <var class="Arg">tab</var>, <var class="Arg">bch</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a Brauer character</p>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsGaloisInvariant</code>( <var class="Arg">tab</var>, <var class="Arg">bch</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code></p>

<p>The argument <var class="Arg">tab</var> must be a Brauer character table for which the Brauer characters are defined with respect to the lift given by Conway polynomials. And <var class="Arg">bch</var> must be an irreducible Brauer character of this table.</p>

<p>The function <code class="func">StandardValuesBrauerCharacter</code> recomputes the values corresponding to the lift given by <code class="func">StandardCyclicGenerator</code> (<a href="chap3.html#X79D3165F833F28DA"><span class="RefLink">3.1-1</span></a>), provided that the Conway polynomials for computing the Frobenius character values of <var class="Arg">bch</var> are available. If Conway polynomials are missing the corresponding character values are substituted by <code class="keyw">fail</code>. If the result does not contain <code class="keyw">fail</code> it is a class function which is Galois conjugate to <var class="Arg">bch</var> (see <code class="func">GaloisCyc</code> (<a href="../../../doc/ref/chap72.html#X856AB97E785E0B04"><span class="RefLink">Reference: GaloisCyc for a class function</span></a>)).</p>

<p>The utility <code class="func">IsGaloisInvariant</code> returns <code class="keyw">true</code> if all Galois conjugates of <var class="Arg">bch</var> are Brauer characters in <var class="Arg">tab</var>. If this is the case then different lifts will permute the Galois conjugates and all of them are Brauer characters with respect to any lift.</p>

<p>WARNING: The result of this function may not be a valid Brauer character for the table <var class="Arg">tab</var> (that is an integer linear combination of irreducible Brauer characters in <var class="Arg">tab</var>). For a proper handling of several lifts the data structure of Brauer character tables needs to be extended (it must refer to the lift), and then the result of this function should return a Brauer character of another table that refers to another lift.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">tab := BrauerTable("M", 19);</span>
BrauerTable( "M", 19 )
<span class="GAPprompt">gap></span> <span class="GAPinput"># cannot translate some values to different lift</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fail in AsList(StandardValuesBrauerCharacter(tab, Irr(tab)[16]));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput"># but table contains the irreducible Brauer characters for any lift</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll(Irr(tab), bch-> IsGaloisInvariant(tab, bch));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">tab := BrauerTable("A18", 3);</span>
BrauerTable( "A18", 3 )
<span class="GAPprompt">gap></span> <span class="GAPinput"># here different lifts lead to different Brauer character tables</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">bch := Irr(tab)[38];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGaloisInvariant(tab, bch);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">new := StandardValuesBrauerCharacter(tab, bch);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fail in AsList(new);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">Position(Irr(tab), new);</span>
fail
</pre></div>

<p>The inverse of a lift is used to reduce character values in characteristic <span class="SimpleMath">0</span> modulo a prime <span class="SimpleMath">p</span>. Choosing a lift is equivalent to choosing a <span class="SimpleMath">p</span>-modular system. <strong class="pkg">GAP</strong> has the function <code class="func">FrobeniusCharacterValue</code> (<a href="../../../doc/ref/chap72.html#X79BACBC47B4C413E"><span class="RefLink">Reference: FrobeniusCharacterValue</span></a>) which computes this reduction with respect to the lift defined by Conway polynomials.</p>

<p>Here is the corresponding function with respect to the lift constructed in this package.</p>

<p><a id="X814BE20A81F82969" name="X814BE20A81F82969"></a></p>

<h5>4.7-2 <span class="Heading">Frobenius character values</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallestDegreeFrobeniusCharacterValue</code>( <var class="Arg">cyc</var>, <var class="Arg">p</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a positive integer or <code class="keyw">fail</code></p>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardFrobeniusCharacterValue</code>( <var class="Arg">cyc</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an element of <var class="Arg">F</var> or <code class="keyw">fail</code></p>

<p>The argument <var class="Arg">cyc</var> must be a cyclotomic whose conductor and denominator are not divisible by the prime integer <var class="Arg">p</var> or the characteristic of the standard finite field <var class="Arg">F</var>.</p>

<p>The order of the multiplicative group of <var class="Arg">F</var> must be divisible by the conductor of <var class="Arg">cyc</var>.</p>

<p>Then <code class="func">StandardFrobeniusCharacterValue</code> returns the image of <var class="Arg">cyc</var> in <var class="Arg">F</var> under the homomorphism which maps the root of unity <code class="code">E(n)</code> to the <code class="func">StandardCyclicGenerator</code> (<a href="chap3.html#X79D3165F833F28DA"><span class="RefLink">3.1-1</span></a>) of order <code class="code">n</code> in <var class="Arg">F</var>. If the conditions are not fulfilled the function returns <code class="keyw">fail</code>.</p>

<p>The function <code class="func">SmallestDegreeFrobeniusCharacterValue</code> returns the smallest degree of a field over the prime field of order <var class="Arg">p</var> containing the image of <var class="Arg">cyc</var>.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">SmallestDegreeFrobeniusCharacterValue(E(13), 19);</span>
12
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FF(19,12);</span>
FF(19, 12)
<span class="GAPprompt">gap></span> <span class="GAPinput">x := StandardFrobeniusCharacterValue(E(13),F);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x^13;</span>
ZZ(19,12,[1])
<span class="GAPprompt">gap></span> <span class="GAPinput">x = StandardCyclicGenerator(F, 13);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">cc := (E(13)+1/3)^4;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">xx := StandardFrobeniusCharacterValue(cc, F);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">xx = StandardFrobeniusCharacterValue(E(13)+1/3, F)^4;</span>
true
</pre></div>

<p><a id="X78ED090878CEE6AA" name="X78ED090878CEE6AA"></a></p>

<h4>4.8 <span class="Heading">Known factorizations of multiplicative group orders</span></h4>

<p><a id="X7BAF533D86DAD073" name="X7BAF533D86DAD073"></a></p>

<h5>4.8-1 CANFACT</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CANFACT</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This variable contains a list where for each prime <span class="SimpleMath">p < 10000</span> the entry <code class="code">CANFACT[p]</code> holds a list of integers <span class="SimpleMath">i</span> such that the number <span class="SimpleMath">p^i-1</span> (the order of the multiplicative group of the finite field <code class="code">FF(p,i)</code>) can be factored by <strong class="pkg">GAP</strong> in a short time. This is based on the enormous efforts to find factors of numbers of this form, see <a href="chapBib.html#biBBrentFactors">[Cro]</a>.</p>

<p>For <span class="SimpleMath">p < 10</span> the range of considered exponents is <span class="SimpleMath">2 ≤ i ≤ 2000</span>, for <span class="SimpleMath">10 < p < 100</span> it is <span class="SimpleMath">2 ≤ i ≤ 500</span>, and for <span class="SimpleMath">100 < p < 10000</span> it is <span class="SimpleMath">2 ≤ i ≤ 100</span>.</p>

<p>These data describe (in May 2022) <span class="SimpleMath">112968</span> pairs <code class="code">p, i</code> such that <code class="code">StandardPrimitiveRoot(FF(p,i))</code> can be computed in reasonable time. Only for <span class="SimpleMath">10858</span> of these cases <strong class="pkg">GAP</strong> knows or can easily compute the corresponding Conway polynomial (see <code class="func">ConwayPolynomial</code> (<a href="../../../doc/ref/chap59.html#X7C2425A786F09054"><span class="RefLink">Reference: ConwayPolynomial</span></a>)).</p>

<p>The current content of <code class="code">CANFACT</code> was generated after updating the data in the <strong class="pkg">FactInt</strong> package concerning factors of numbers of the form <span class="SimpleMath">a^n ± 1</span>. If you want to use that list you should also update your <strong class="pkg">GAP</strong> installation with:</p>


<div class="example"><pre>
FetchMoreFactors(
  "https://maths-people.anu.edu.au/~brent/ftp/factors/factors.gz",
  false);
FetchMoreFactors(
  "http://myfactorcollection.mooo.com:8090/brentdata/May31_2022/factors.gz",
  true);
</pre></div>

<p><a id="X7D85D01D7F846000" name="X7D85D01D7F846000"></a></p>

<h4>4.9 <span class="Heading">Some loops for  <strong class="pkg">StandardFF</strong></span></h4>

<p><a id="X788898E979B9E9D9" name="X788898E979B9E9D9"></a></p>

<h5>4.9-1 <span class="Heading">Computing all fields in various ranges</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AllPrimeDegreePolynomials</code>( <var class="Arg">p</var>, <var class="Arg">bound</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AllFF</code>( <var class="Arg">p</var>, <var class="Arg">bound</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AllPrimitiveRoots</code>( <var class="Arg">p</var>, <var class="Arg">bound</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AllPrimitiveRootsCANFACT</code>(  )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AllFieldsWithConwayPolynomial</code>( [<var class="Arg">"ConwayGen"</var>][,] [<var class="Arg">"MiPo"</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>These function compute all fields in some range, sometimes with further data. All functions return a list with some timings and print a log-file in the current directory.</p>

<p><code class="func">AllPrimeDegreePolynomials</code> computes all irreducible polynomials of prime degree needed for the construction of all finite fields of order <span class="SimpleMath"><var class="Arg">p</var>^i</span>, <span class="SimpleMath">1 ≤ i ≤ <var class="Arg">bound</var></span>. This is the most time consuming part in the construction of the fields.</p>

<p><code class="func">AllFF</code> computes all <code class="code">FF(p,i)</code> for <span class="SimpleMath">1 ≤ i ≤ <var class="Arg">bound</var></span>. When the previous function was called before for the same range, this function spends most of its time by computing the minimal polynomials of the standardized primitive elements of <code class="code">FF(p,i)</code>.</p>

<p><code class="func">AllPrimitiveRoots</code> computes the standardized primitive roots in <code class="code">FF(p,i)</code> for <span class="SimpleMath">1 ≤ i ≤ <var class="Arg">bound</var></span>. The most time consuming cases are when a large prime divisor <span class="SimpleMath">r</span> of <span class="SimpleMath">p^i-1</span> already divides <span class="SimpleMath">p^j-1</span> for some <span class="SimpleMath">j < i</span> (but then <span class="SimpleMath">r</span> divides <span class="SimpleMath">i/j</span>). Cases where <strong class="pkg">GAP</strong> cannot factorize <span class="SimpleMath">p^i-1</span> (that is <span class="SimpleMath">i</span> is not contained in <code class="code">CANFACT[p]</code>) are skipped.</p>

<p><code class="func">AllPrimitiveRootsCANFACT</code> does the same as the previous function for all pairs <span class="SimpleMath">p, i</span> stored in <code class="func">CANFACT</code> (<a href="chap4.html#X7BAF533D86DAD073"><span class="RefLink">4.8-1</span></a>).</p>

<p><code class="func">AllFieldsWithConwayPolynomial</code> computes all <code class="code">FF(p,i)</code> for the cases where <strong class="pkg">GAP</strong> knows the precomputed <code class="code">ConwayPolynomial(p,i)</code>. With the optional argument <code class="code">"ConwayGen the function computes for all fields the SteinitzPairConwayGenerator (4.4-3) and writes it into a file SteinitzPairConway. With the optional argument "MiPo" the function also computes the minimal polynomials of the StandardPrimitiveRoot (3.1-1) and writes it to a file MiPoPrimitiveRoots (these polynomials have the same compatibility properties as Conway polynomials).



<p><a id="X7EA72E8A78A4ADE2" name="X7EA72E8A78A4ADE2"></a></p>

<h4>4.10 <span class="Heading">Undocumented features</span></h4>

<p>We mention some features of this package which may be temporary, vanish or changed.</p>

<p>A directory <code class="file">ntl</code> contains some simple standalone programs which use the library NTL <a href="chapBib.html#biBNTL">[Sho]</a>. There is a function <code class="code">StandardIrreducibleCoeffListNTL(K, d, a)</code> which can be used instead of <code class="code">StandardIrreducibleCoeffListNTL(K, d, a)</code> when <code class="code">K</code> is a prime field. This gives a good speedup for not too small <code class="code">d</code>, say <code class="code">d</code> <span class="SimpleMath">>500</span>.</p>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chapBib.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.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>

95%


¤ Dauer der Verarbeitung: 0.31 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.