Quelle chap3.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/standardff/doc/chap3.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 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.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="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

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

<div class="ContSSBlock">
 <a href="chap3.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.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.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.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.html#X80DCBB4F84F04DDB">2.2-1</a>)) and <var class="Arg">m</var> a positive integer. If <var class="Arg">m</var> does not divide |<var class="Arg">F</var>| - 1 the function returns <code class="keyw">fail</code>. Otherwise a standardized element x_<var class="Arg">m</var> 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 |<var class="Arg">F</var>| - 1. In this case x_<var class="Arg">m</var> 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.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <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 />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality96%

¤ Dauer der Verarbeitung: 0.16 Sekunden (vorverarbeitet) ¤

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.