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 |F| - 1 the function returns fail. Otherwise a standardized element x_m of order m is returned, as described above.

The argument m is optional, if not given its default value is |F| - 1. In this case x_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