GAP (StandardFF) - Chapter 3: Standard generators of cyclic groups

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 [Lüb23] we define standardized generators \(x_m\) of these cyclic groups in the standard finite fields described in chapter 2 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 FF(p,n) 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 FF(p,n) 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 FF(p,n) and FF(p,l) (considered as subfield of FF(p,n)), 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 ConwayPolynomial (Reference: ConwayPolynomial).

3.1-1 StandardCyclicGenerator

The argument F must be a standard finite field (see FF (2.2-1)) and m a positive integer. If m does not divide \(|\textit{F}| - 1\) the function returns fail. Otherwise a standardized element \(x_{\textit{m}}\) of order m is returned, as described above.

The argument m 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 StandardPrimitiveRoot.

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)

3 Standard generators of cyclic groups

3.1 Generators of multiplicative groups

3.1-1 StandardCyclicGenerator