Quelle chap3_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/standardff/doc/chap3_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 (StandardFF) - Chapter 3: Standard generators of cyclic groups</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="chap3" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <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="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="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>

<a href="chap3.html">[MathJax off]</a>
<a id="X7C788F1583FB8544" name="X7C788F1583FB8544"></a>
<div class="ChapSects"><a href="chap3_mj.html#X7C788F1583FB8544">3 Standard generators of cyclic groups</a>
<div class="ContSect"> <a href="chap3_mj.html#X864390D67EA526FA">3.1 Generators of multiplicative groups</a>

<div class="ContSSBlock">
 <a href="chap3_mj.html#X79D3165F833F28DA">3.1-1 StandardCyclicGenerator</a>
</div></div>
</div>

<h3>3 Standard generators of cyclic groups</h3>

<a id="X864390D67EA526FA" name="X864390D67EA526FA"></a>

<h4>3.1 Generators of multiplicative groups</h4>

The multiplicative group of each finite field is cyclic and so for each divisor \(m\) of its order there is a unique subgroup of order \(m\).

In <a href="chapBib_mj.html#biBStdFFCyc">[Lüb23]</a> we define standardized generators \(x_m\) of these cyclic groups in the standard finite fields described in chapter <a href="chap2_mj.html#X7D1270E8831F128E">2</a> which fulfill the following compatibility condition: If \(k | m\) then \(x_m^{{m/k}} = x_k\).

The condition that \(x_m\) can be computed is that \(m\) can be factorized. (If we do not know the prime divisors of \(m\) then we cannot show that a given element has order \(m\).) Note that this means that we can compute \(x_m\) in <code class="code">FF(p,n)</code> when \(m | (p^n -1)\) and we know the prime divisors of \(m\), even when the factorization of \((p^n-1)\) is not known.

In the case that the factorization of \(m = p^n-1\) is known the corresponding \(x_m\) is a standardized primitive root of <code class="code">FF(p,n)</code> that can be computed.

Let \(l | n\) and set \(m = p^n-1\) and \(k = p^l-1\). Then \(x_m\) and \(x_k\) are the standard primitive roots of <code class="code">FF(p,n)</code> and <code class="code">FF(p,l)</code> (considered as subfield of <code class="code">FF(p,n)</code>), respectively. The compatibity condition says that \(x_m^{{m/k}} = x_k\). This shows that the minimal polynomials of \(x_m\) and \(x_k\) over the prime field fulfill the same compatibility conditions as Conway polynomials (see <code class="func">ConwayPolynomial</code> (<a href="../../../doc/ref/chap59_mj.html#X7C2425A786F09054">Reference: ConwayPolynomial</a>).

<a id="X79D3165F833F28DA" name="X79D3165F833F28DA"></a>

<h5>3.1-1 StandardCyclicGenerator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardCyclicGenerator</code>( <var class="Arg">F</var>[, <var class="Arg">m</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardPrimitiveRoot</code>( <var class="Arg">F</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: an element of <var class="Arg">F</var> or <code class="keyw">fail</code>

The argument <var class="Arg">F</var> must be a standard finite field (see <code class="func">FF</code> (<a href="chap2_mj.html#X80DCBB4F84F04DDB">2.2-1</a>)) and <var class="Arg">m</var> a positive integer. If <var class="Arg">m</var> does not divide \(|\textit{F}| - 1\) the function returns <code class="keyw">fail</code>. Otherwise a standardized element \(x_{\textit{m}}\) of order <var class="Arg">m</var> is returned, as described above.

The argument <var class="Arg">m</var> is optional, if not given its default value is \(|\textit{F}| - 1\). In this case \(x_{\textit{m}}\) can also be computed with the attribute <code class="func">StandardPrimitiveRoot</code>.

<div class="example"><pre>gap> F := FF(67, 18); # Conway polynomial was hard to compute
FF(67, 18)
gap> x := PrimitiveElement(F);
ZZ(67,18,[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
gap> xprim := StandardPrimitiveRoot(F);;
gap> k := (Size(F)-1) / Order(x);
6853662165340556076084083497526
gap> xm := StandardCyclicGenerator(F, Order(x));;
gap> xm = xprim^k;
true
gap> F := FF(23, 201); # factorization of (|F| - 1) not known 
FF(23, 201)
gap> m:=79*269*67939;
1443771689
gap> (Size(F)-1) mod m;
0
gap> OrderMod(23, m);
201
gap> xm := StandardCyclicGenerator(F, m);;
gap> IsOne(xm^m);
true
gap> ForAll(Factors(m), r-> not IsOne(xm^(m/r)));
true
gap> F := FF(7,48);
FF(7, 48)
gap> K := FF(7,12);
FF(7, 12)
gap> emb := Embedding(K, F);;
gap> x := StandardPrimitiveRoot(F);;
gap> y := StandardPrimitiveRoot(K);;
gap> y^emb = x^((Size(F)-1)/(Size(K)-1));
true
gap> v := Indeterminate(FF(7,1), "v");
v
gap> px := MinimalPolynomial(FF(7,1), x, v);;
gap> py := MinimalPolynomial(FF(7,1), y, v);;
gap> Value(py, PowerMod(v, (Size(F)-1)/(Size(K)-1), px)) mod px;
0*Z(7)
</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <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="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality98%

¤ Dauer der Verarbeitung: 0.9 Sekunden ¤

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.