In this section we will show how one can add a new type of group elements to GAP. A lot of group elements in GAP are implemented this way, for example elements of generic factor groups, or elements of generic direct products.
We will use prime residue classes modulo an integer as our example. They have the advantage that the arithmetic is very simple, so that we can concentrate on the implementation without being carried away by mathematical details.
Note that everything we define is already in the library in the file
LIBNAME/"numtheor.g", so there is no need for you to type it in. You
may however like to make a copy of this file and modify it.
We will represent residue classes by records. This is absolutely typical, all group elements not built into the GAP kernel are realized by records.
To distinguish records representing residue classes from other records we
require that residue class records have a component with the name
isResidueClass and the value true. We also require that they have a
component with the name isGroupElement and again the value true.
Those two components are called the tag components.
Next each residue class record must of course have components that tell
us which residue class this record represents. The component with the
name representative contains the smallest nonnegative element of the
residue class. The component with the name modulus contains the
modulus. Those two components are called the identifying components.
Finally each residue class record must have a component with the name
operations that contains an appropriate operations record (see below).
In this way we can make use of the possibility to define operations for
records (see Comparisons of Records and Operations for Records).
Below is an example of a residue class record.
r13mod43 := rec(
isGroupElement := true,
isResidueClass := true,
representative := 13,
modulus := 43,
domain := GroupElements,
operations := ResidueClassOps );
The first function that we have to write is very simple. Its only task
is to test whether an object is a residue class. It does this by testing
for the tag component isResidueClass.
gap> IsResidueClass := function ( obj )
> return IsRec( obj )
> and IsBound( obj.isResidueClass )
> and obj.isResidueClass;
> end;;
Our next function takes a representative and a modulus and constructs a new residue class. Again this is not very difficult.
gap> ResidueClass := function ( representative, modulus )
> local res;
> res := rec();
> res.isGroupElement := true;
> res.isResidueClass := true;
> res.representative := representative mod modulus;
> res.modulus := modulus;
> res.domain := GroupElements;
> res.operations := ResidueClassOps;
> return res;
> end;;
Now we have to define the operations record for residue classes.
Remember that this record contains a function for each binary operation,
Comparisons of Records and Operations for Records). The operations =, <, *,
/, mod, ^, Comm, and Order are the ones that are applicable to
all group elements. The meaning of those operations for group elements
Operations for Group Elements.
Luckily we do not have to define everything. Instead we can inherit a
lot of those functions from generic group elements. For example, for all
group elements g/h should be equivalent to g*h^-1. So the
function for / could simply be function(g,h) return g*h^-1; end.
Note that this function can be applied to all group elements,
independently of their type, because all the dependencies are in * and
^.
The operations record GroupElementOps contains such functions that can
be used by all types of group elements. Note that there is no element
that has GroupElementsOps as its operations record. This is
impossible, because there is for example no generic method to multiply or
invert group elements. Thus GroupElementsOps is only used to inherit
general methods as is done below.
gap> ResidueClassOps := Copy( GroupElementOps );;
Note that the copy is necessary, otherwise the following assignments
would not only change ResidueClassOps but also GroupElementOps.
The first function we are implementing is the equality comparison. The
required operation is described simply enough. = should evaluate to
true if the operands are equal and false otherwise. Two residue
classes are of course equal if they have the same representative and the
same modulus. One complication is that when this function is called
either operand may not be a residue class. Of course at least one must
be a residue class otherwise this function would not have been called at
all.
gap> ResidueClassOps.\= := function ( l, r )
> local isEql;
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> isEql := l.representative = r.representative
> and l.modulus = r.modulus;
> else
> isEql := false;
> fi;
> else
> if IsResidueClass( r ) then
> isEql := false;
> else
> Error("panic, neither <l> nor <r> is a residue class");
> fi;
> fi;
> return isEql;
> end;;
Note that the quotes around the equal sign = are necessary, otherwise
it would not be taken as a record component name, as required, but as the
symbol for equality, which must not appear at this place.
Note that we do not have to implement a function for the inequality
operator <, because it is in the GAP kernel implemented by the
equivalence l < r is not l = r.
The next operation is the comparison. We define that one residue class is smaller than another residue class if either it has a smaller modulus or, if the moduli are equal, it has a smaller representative. We must also implement comparisons with other objects.
gap> ResidueClassOps.\< := function ( l, r )
> local isLess;
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> isLess := l.representative < r.representative
> or (l.representative = r.representative
> and l.modulus < r.modulus);
> else
> isLess := not IsInt( r ) and not IsRat( r )
> and not IsCyc( r ) and not IsPerm( r )
> and not IsWord( r ) and not IsAgWord( r );
> fi;
> else
> if IsResidueClass( r ) then
> isLess := IsInt( l ) or IsRat( l )
> or IsCyc( l ) or IsPerm( l )
> or IsWord( l ) or IsAgWord( l );
> else
> Error("panic, neither <l> nor <r> is a residue class");
> fi;
> fi;
> return isLess;
> end;;
The next operation that we must implement is the multiplication *.
This function is quite complex because it must handle several different
tasks. To make its implementation easier to understand we will start
with a very simple--minded one, which only multiplies residue classes,
and extend it in the following paragraphs.
gap> ResidueClassOps.\* := function ( l, r )
> local prd; # product of l and r, result
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> if l.modulus <> r.modulus then
> Error("<l> and <r> must have the same modulus");
> fi;
> prd := ResidueClass(
> l.representative * r.representative,
> l.modulus );
> else
> Error("product of <l> and <r> must be defined");
> fi;
> else
> if IsResidueClass( r ) then
> Error("product of <l> and <r> must be defined");
> else
> Error("panic, neither <l> nor <r> is a residue class");
> fi;
> fi;
> return prd;
> end;;
This function correctly multiplies residue classes, but there are other products that must be implemented. First every group element can be multiplied with a list of group elements, and the result shall be the Operations for Lists). In such a case the above function would only signal an error, which is not acceptable. Therefore we must extend this definition.
gap> ResidueClassOps.\* := function ( l, r )
> local prd; # product of l and r, result
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> if l.modulus <> r.modulus then
> Error( "<l> and <r> must have the same modulus" );
> fi;
> prd := ResidueClass(
> l.representative * r.representative,
> l.modulus );
> elif IsList( r ) then
> prd := List( r, x -> l * x );
> else
> Error("product of <l> and <r> must be defined");
> fi;
> elif IsList( l ) then
> if IsResidueClass( r ) then
> prd := List( l, x -> x * r );
> else
> Error("panic: neither <l> nor <r> is a residue class");
> fi;
> else
> if IsResidueClass( r ) then
> Error( "product of <l> and <r> must be defined" );
> else
> Error("panic, neither <l> nor <r> is a residue class");
> fi;
> fi;
> return prd;
> end;;
This function is almost complete. However it is also allowed to multiply
a group element with a subgroup and the result shall be a coset (see
RightCoset). The operations record of subgroups, which are of course
also represented by records (see Group Records), contains a function
that constructs such a coset. The problem is that in an expression like
subgroup * residue-class, this function is not called. This is
because the multiplication function in the operations record of the
right operand is called if both operands have such a function (see
Operations for Records). Now in the above case both operands have such
a function. The left operand subgroup has the operations record
GroupOps (or some refinement thereof), the right operand
residue-class has the operations record ResidueClassOps. Thus
ResidueClassOps.* is called. But it does not and also should not know
how to construct a coset. The solution is simple. The multiplication
function for residue classes detects this special case and simply calls
the multiplication function of the left operand.
gap> ResidueClassOps.\* := function ( l, r )
> local prd; # product of l and r, result
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> if l.modulus <> r.modulus then
> Error( "<l> and <r> must have the same modulus" );
> fi;
> prd := ResidueClass(
> l.representative * r.representative,
> l.modulus );
> elif IsList( r ) then
> prd := List( r, x -> l * x );
> else
> Error("product of <l> and <r> must be defined");
> fi;
> elif IsList( l ) then
> if IsResidueClass( r ) then
> prd := List( l, x -> x * r );
> else
> Error("panic: neither <l> nor <r> is a residue class");
> fi;
> else
> if IsResidueClass( r ) then
> if IsRec( l ) and IsBound( l.operations )
> and IsBound( l.operations.\* )
> and l.operations.\* <> ResidueClassOps.\*
> then
> prd := l.operations.\*( l, r );
> else
> Error("product of <l> and <r> must be defined");
> fi;
> else
> Error("panic, neither <l> nor <r> is a residue class");
> fi;
> fi;
> return prd;
> end;;
Now we are done with the multiplication.
Next is the powering operation ^. It is not very complicated. The
PowerMod function (see PowerMod) does most of what we need,
especially the inversion of elements with the Euclidean algorithm when
the exponent is negative. Note however, that the definition of
operations (see Operations for Group Elements) requires that the
conjugation is available as power of a residue class by another residue
class. This is of course very easy since residue classes form an abelian
group.
gap> ResidueClassOps.\^ := function ( l, r )
> local pow;
> if IsResidueClass( l ) then
> if IsResidueClass( r ) then
> if l.modulus <> r.modulus then
> Error("<l> and <r> must have the same modulus");
> fi;
> if GcdInt( r.representative, r.modulus ) <> 1 then
> Error("<r> must be invertable");
> fi;
> pow := l;
> elif IsInt( r ) then
> pow := ResidueClass(
> PowerMod( l.representative, r, l.modulus ),
> l.modulus );
> else
> Error("power of <l> and <r> must be defined");
> fi;
> else
> if IsResidueClass( r ) then
> Error("power of <l> and <r> must be defined");
> else
> Error("panic, neither <l> nor <r> is a residue class");
> fi;
> fi;
> return pow;
> end;;
The last function that we have to write is the printing function. This
is called to print a residue class. It prints the residue class in the
form ResidueClass( representative, modulus ). It is fairly typical
to print objects in such a form. This form has the advantage that it can
be read back, resulting in exactly the same element, yet it is very
concise.
gap> ResidueClassOps.Print := function ( r )
> Print("ResidueClass( ",r.representative,", ",r.modulus," )");
> end;;
Now we are done with the definition of residue classes as group elements. Try them. We can at this point actually create groups of such elements, and compute in them.
However, we are not yet satisfied. There are two problems with the code we have implemented so far. Different people have different opinions about which of those problems is the graver one, but hopefully all agree that we should try to attack those problems.
The first problem is that it is still possible to define objects via
Group (see Group) that are not actually groups.
gap> G := Group( ResidueClass(13,43), ResidueClass(13,41) );
Group( ResidueClass( 13, 43 ), ResidueClass( 13, 41 ) )
The other problem is that groups of residue classes constructed with the code we have implemented so far are not handled very efficiently. This is because the generic group algorithms are used, since we have not implemented anything else. For example to test whether a residue class lies in a residue class group, all elements of the residue class group are computed by a Dimino algorithm, and then it is tested whether the residue class is an element of this proper set.
To solve the first problem we must first understand what happens with the
above code if we create a group with Group( res1, res2... ).
Group tries to find a domain that contains all the elements res1,
res2, etc. It first calls Domain( [ res1, res2... ] ) (see
Domain). Domain looks at the residue classes and sees that they all
are records and that they all have a component with the name domain.
This is understood to be a domain in which the elements lie. And in fact
res1 in GroupElements is true, because GroupElements accepts all
records with tag isGroupElement. So Domain returns GroupElements.
Group then calls
GroupElements.operations.Group(GroupElements,[res1,res2...],id),
where id is the identity residue class, obtained by res1 ^ 0, and
returns the result.
GroupElementsOps.Group is the function that actually creates the group.
It does this by simply creating a record with its second argument as
generators list, its third argument as identity, and the generic
GroupOps as operations record. It ignores the first argument, which is
passed only because convention dictates that a dispatcher passes the
domain as first argument.
So to solve the first problem we must achieve that another function
instead of the generic function GroupElementsOps.Group is called. This
can be done by persuading Domain to return a different domain. And
this will happen if the residue classes hold this other domain in their
domain component.
The obvious choice for such a domain is the (yet to be written) domain
ResidueClasses. So ResidueClass must be slightly changed.
gap> ResidueClass := function ( representative, modulus )
> local res;
> res := rec();
> res.isGroupElement := true;
> res.isResidueClass := true;
> res.representative := representative mod modulus;
> res.modulus := modulus;
> res.domain := ResidueClasses;
> res.operations := ResidueClassOps;
> return res;
> end;;
The main purpose of the domain ResidueClasses is to construct groups,
so there is very little we have to do. And in fact most of that can be
inherited from GroupElements.
gap> ResidueClasses := Copy( GroupElements );;
gap> ResidueClasses.name := "ResidueClasses";;
gap> ResidueClassesOps := Copy( GroupElementsOps );;
gap> ResidueClasses.operations := ResidueClassesOps;;
So now we must implement ResidueClassesOps.Group, which should check
whether the passed elements do in fact form a group. After checking it
simply delegates to the generic function GroupElementsOps.Group to
create the group as before.
gap> ResidueClassesOps.Group := function ( ResidueClasses, gens, id )
> local g; # one generator from gens
> for g in gens do
> if g.modulus <> id.modulus then
> Error("the generators must all have the same modulus");
> fi;
> if GcdInt( g.representative, g.modulus ) <> 1 then
> Error("the generators must all be prime residue classes");
> fi;
> od;
> return GroupElementOps.Group( ResidueClasses, gens, id );
> end;;
This solves the first problem. To solve the second problem, i.e., to
make operations with residue class groups more efficient, we must extend
the function ResidueClassesOps.Group. It now enters a new operations
record into the group. It also puts the modulus into the group record,
so that it is easier to access.
gap> ResidueClassesOps.Group := function ( ResidueClasses, gens, id )
> local G, # group G, result
> gen; # one generator from gens
> for gen in gens do
> if gen.modulus <> id.modulus then
> Error("the generators must all have the same modulus");
> fi;
> if GcdInt( gen.representative, gen.modulus ) <> 1 then
> Error("the generators must all be prime residue classes");
> fi;
> od;
> G := GroupElementsOps.Group( ResidueClasses, gens, id );
> G.modulus := id.modulus;
> G.operations := ResidueClassGroupOps;
> return G;
> end;;
Of course now we must build such an operations record. Luckily we do not
have to implement all functions, because we can inherit a lot of
functions from GroupOps. This is done by copying GroupOps as we have
done before for ResidueClassOps and ResidueClassesOps.
gap> ResidueClassGroupOps := Copy( GroupOps );;
Now the first function that we must write is the Subgroup function to
ensure that not only groups constructed by Group have the correct
operations record, but also subgroups of those groups created by
Subgroup. As in Group we only check the arguments and then leave the
work to GroupOps.Subgroup.
gap> ResidueClassGroupOps.Subgroup := function ( G, gens )
> local S, # subgroup of G, result
> gen; # one generator from gens
> for gen in gens do
> if gen.modulus <> G.modulus then
> Error("the generators must all have the same modulus");
> fi;
> if GcdInt( gen.representative, gen.modulus ) <> 1 then
> Error("the generators must all be prime residue classes");
> fi;
> od;
> S := GroupOps.Subgroup( G, gens );
> S.modulus := G.modulus;
> S.operations := ResidueClassGroupOps;
> return S;
> end;;
The first function that we write especially for residue class groups is
SylowSubgroup. Since residue class groups are abelian we can compute a
Sylow subgroup of such a group by simply taking appropriate powers of the
generators.
gap> ResidueClassGroupOps.SylowSubgroup := function ( G, p )
> local S, # Sylow subgroup of G, result
> gen, # one generator of G
> ord, # order of gen
> gens; # generators of S
> gens := [];
> for gen in G.generators do
> ord := OrderMod( gen.representative, G.modulus );
> while ord mod p = 0 do ord := ord / p; od;
> Add( gens, gen ^ ord );
> od;
> S := Subgroup( Parent( G ), gens );
> return S;
> end;;
To allow the other functions that are applicable to residue class groups to work efficiently we now want to make use of the fact that residue class groups are direct products of cyclic groups and that we know what those factors are and how we can project onto those factors.
To do this we write ResidueClassGroupOps.MakeFactors that adds the
components facts, roots, sizes, and sgs to the group record G.
This information, detailed below, will enable other functions to work
efficiently with such groups. Creating such information is a fairly
typical thing, for example for permutation groups the corresponding
information is the stabilizer chain computed by MakeStabChain.
G.facts will be the list of prime power factors of G.modulus.
Actually this is a little bit more complicated, because the residue class
group modulo the largest power q of 2 that divides G.modulus need
not be cyclic. So if q is a multiple of 4, G.facts[1] will be 4,
corresponding to the projection of G into (Z / 4 Z)^* (of size 2),
furthermore if q is a multiple of 8, G.facts[2] will be q,
corresponding to the projection of G into the subgroup generated by 5
in (Z / q Z)^* (of size q/4).
G.roots will be a list of primitive roots, i.e., of generators of the
corresponding factors in G.facts. G.sizes will be a list of the
sizes of the corresponding factors in G.facts, i.e., G.sizes[i]
= Phi( G.facts[i] ). (If G.modulus is a multiple of 8,
G.roots[2] will be 5, and G.sizes[2] will be q/4.)
Now we can represent each element g of the group G by a list e,
called the exponent vector, of the length of G.facts, where
e[i] is the logarithm of g.representative mod G.facts[i]
with respect to G.roots[i]. The multiplication of elements of G
corresponds to the componentwise addition of their exponent vectors,
where we add modulo G.sizes[i] in the i-th component. (Again
special consideration are necessary if G.modulus is divisible by 8.)
Next we compute the exponent vectors of all generators of G, and
represent this information as a matrix. Then we bring this matrix into
upper triangular form, with an algorithm that is very much like the
ordinary Gaussian elimination, modified to account for the different
sizes of the components. This upper triangular matrix of exponent
vectors is the component G.sgs. This new matrix obviously still
contains the exponent vectors of a generating system of G, but a much
nicer one, which allows us to tackle problems one component at a time.
(It is not necessary that you fully check this, the important thing here
is not the mathematical side.)
gap> ResidueClassGroupOps.MakeFactors := function ( G )
> local p, q, # prime factor of modulus and largest power
> r, s, # two rows of the standard generating system
> g, # extended gcd of leading entries in r, s
> x, y, # two entries in r and s
> i, k, l; # loop variables
>
> # find the factors of the direct product
> G.facts := [];
> G.roots := [];
> G.sizes := [];
> for p in Set( Factors( G.modulus ) ) do
> q := p;
> while G.modulus mod (p*q) = 0 do q := p*q; od;
> if q mod 4 = 0 then
> Add( G.facts, 4 );
> Add( G.roots, 3 );
> Add( G.sizes, 2 );
> fi;
> if q mod 8 = 0 then
> Add( G.facts, q );
> Add( G.roots, 5 );
> Add( G.sizes, q/4 );
> fi;
> if p <> 2 then
> Add( G.facts, q );
> Add( G.roots, PrimitiveRootMod( q ) );
> Add( G.sizes, (p-1)*q/p );
> fi;
> od;
>
> # represent each generator in this factorization
> G.sgs := [];
> for k in [ 1 .. Length( G.generators ) ] do
> G.sgs[k] := [];
> for i in [ 1 .. Length( G.facts ) ] do
> if G.facts[i] mod 8 = 0 then
> if G.generators[k].representative mod 4 = 1 then
> G.sgs[k][i] := LogMod(
> G.generators[k].representative,
> G.roots[i], G.facts[i] );
> else
> G.sgs[k][i] := LogMod(
> -G.generators[k].representative,
> G.roots[i], G.facts[i] );
> fi;
> else
> G.sgs[k][i] := LogMod(
> G.generators[k].representative,
> G.roots[i], G.facts[i] );
> fi;
> od;
> od;
> for i in [ Length( G.sgs ) + 1 .. Length( G.facts ) ] do
> G.sgs[i] := 0 * G.facts;
> od;
>
> # bring this matrix to diagonal form
> for i in [ 1 .. Length( G.facts ) ] do
> r := G.sgs[i];
> for k in [ i+1 .. Length( G.sgs ) ] do
> s := G.sgs[k];
> g := Gcdex( r[i], s[i] );
> for l in [ i .. Length( r ) ] do
> x := r[l]; y := s[l];
> r[l] := (g.coeff1 * x + g.coeff2 * y) mod G.sizes[l];
> s[l] := (g.coeff3 * x + g.coeff4 * y) mod G.sizes[l];
> od;
> od;
> s := [];
> x := G.sizes[i] / GcdInt( G.sizes[i], r[i] );
> for l in [ 1 .. Length( r ) ] do
> s[l] := (x * r[l]) mod G.sizes[l];
> od;
> Add( G.sgs, s );
> od;
>
> end;;
With the information computed by MakeFactors it is now of course very
easy to compute the size of a residue class group. We just look at the
G.sgs, and multiply the orders of the leading exponents of the
nonzero exponent vectors.
gap> ResidueClassGroupOps.Size := function ( G )
> local s, # size of G, result
> i; # loop variable
> if not IsBound( G.facts ) then
> G.operations.MakeFactors( G );
> fi;
> s := 1;
> for i in [ 1 .. Length( G.facts ) ] do
> s := s * G.sizes[i] / GcdInt( G.sizes[i], G.sgs[i][i] );
> od;
> return s;
> end;;
The membership test is a little bit more complicated. First we test that
the first argument is really a residue class with the correct modulus.
Then we compute the exponent vector of this residue class and reduce this
exponent vector using the upper triangular matrix G.sgs.
gap> ResidueClassGroupOps.\in := function ( res, G )
> local s, # exponent vector of res
> g, # extended gcd
> x, y, # two entries in s and G.sgs[i]
> i, l; # loop variables
> if not IsResidueClass( res )
> or res.modulus <> G.modulus
> or GcdInt( res.representative, res.modulus ) <> 1
> then
> return false;
> fi;
> if not IsBound( G.facts ) then
> G.operations.MakeFactors( G );
> fi;
> s := [];
> for i in [ 1 .. Length( G.facts ) ] do
> if G.facts[i] mod 8 = 0 then
> if res.representative mod 4 = 1 then
> s[i] := LogMod( res.representative,
> G.roots[i], G.facts[i] );
> else
> s[i] := LogMod( -res.representative,
> G.roots[i], G.facts[i] );
> fi;
> else
> s[i] := LogMod( res.representative,
> G.roots[i], G.facts[i] );
> fi;
> od;
> for i in [ 1 .. Length( G.facts ) ] do
> if s[i] mod GcdInt( G.sizes[i], G.sgs[i][i] ) <> 0 then
> return false;
> fi;
> g := Gcdex( s[i], G.sgs[i][i] );
> for l in [ i .. Length( G.facts ) ] do
> x := s[l]; y := G.sgs[i][l];
> s[l] := (g.coeff3 * x + g.coeff4 * y) mod G.sizes[l];
> od;
> od;
> return true;
> end;;
We also add a function Random that works by creating a random exponent
as a random linear combination of the exponent vectors in G.sgs, and
converts this exponent vector to a residue class. (The main purpose of
this function is to allow you to create random test examples for the
other functions.)
gap> ResidueClassGroupOps.Random := function ( G )
> local s, # exponent vector of random element
> r, # vector of remainders in each factor
> i, k, l; # loop variables
> if not IsBound( G.facts ) then
> G.operations.MakeFactors( G );
> fi;
> s := 0 * G.facts;
> for i in [ 1 .. Length( G.facts ) ] do
> l := G.sizes[i] / GcdInt( G.sizes[i], G.sgs[i][i] );
> k := Random( [ 0 .. l-1 ] );
> for l in [ i .. Length( s ) ] do
> s[l] := (s[l] + k * G.sgs[i][l]) mod G.sizes[l];
> od;
> od;
> r := [];
> for l in [ 1 .. Length( s ) ] do
> r[l] := PowerModInt( G.roots[l], s[l], G.facts[l] );
> if G.facts[l] mod 8 = 0 and r[1] = 3 then
> r[l] := G.facts[l] - r[l];
> fi;
> od;
> return ResidueClass( ChineseRem( G.facts, r ), G.modulus );
> end;;
There are a lot more functions that would benefit from being implemented especially for residue class groups. We do not show them here, because the above functions already displayed how such functions can be written.
To round things up, we finally add a function that constructs the full
residue class group given a modulus m. This function is totally
independent of the implementation of residue classes and residue class
groups. It only has to find a (minimal) system of generators of the full
prime residue classes group, and to call Group to construct this group.
It also adds the information entry size to the group record, of course
with the value phi(n).
gap> PrimeResidueClassGroup := function ( m )
> local G, # group Z/mZ, result
> gens, # generators of G
> p, q, # prime and prime power dividing m
> r, # primitive root modulo q
> g; # is = r mod q and = 1 mod m/q
>
> # add generators for each prime power factor q of m
> gens := [];
> for p in Set( Factors( m ) ) do
> q := p;
> while m mod (q * p) = 0 do q := q * p; od;
>
> # (Z/4Z)^* = < 3 >
> if q = 4 then
> r := 3;
> g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
> Add( gens, ResidueClass( g, m ) );
>
> # (Z/8nZ)^* = < 5, -1 > is not cyclic
> elif q mod 8 = 0 then
> r := q-1;
> g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
> Add( gens, ResidueClass( g, m ) );
> r := 5;
> g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
> Add( gens, ResidueClass( g, m ) );
>
> # for odd q, (Z/qZ)^* is cyclic
> elif q <> 2 then
> r := PrimitiveRootMod( q );
> g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
> Add( gens, ResidueClass( g, m ) );
> fi;
>
> od;
>
> # return the group generated by gens
> G := Group( gens, ResidueClass( 1, m ) );
> G.size := Phi( n );
> return G;
> end;;
There is one more thing that we can learn from this example. Mathematically a residue class is not only a group element, but a set as well. We can reflect this in GAP by turning residue classes into domains (see Domains). Section About Defining New Domains gives an example of how to implement a new domain, so we will here only show the code with few comments.
First we must change the function that constructs a residue class, so that it enters the necessary fields to tag this record as a domain. It also adds the information that residue classes are infinite.
gap> ResidueClass := function ( representative, modulus )
> local res;
> res := rec();
> res.isGroupElement := true;
> res.isDomain := true;
> res.isResidueClass := true;
> res.representative := representative mod modulus;
> res.modulus := modulus;
> res.isFinite := false;
> res.size := "infinity";
> res.domain := ResidueClasses;
> res.operations := ResidueClassOps;
> return res;
> end;;
The initialization of the ResidueClassOps record must be changed too,
because now we want to inherit both from GroupElementsOps and
DomainOps. This is done by the function MergedRecord, which takes
two records and returns a new record that contains all components from
either record.
Note that the record returned by MergedRecord does not have those
components that appear in both arguments. This forces us to explicitly
write down from which record we want to inherit those functions, or to
define them anew. In our example the components common to
GroupElementOps and DomainOps are only the equality and ordering
functions, which we have to define anyhow. (This solution for the
problem of which definition to choose in the case of multiple inheritance
is also taken by C++.)
With this function definition we can now initialize ResidueClassOps.
gap> ResidueClassOps := MergedRecord( GroupElementOps, DomainOps );;
Now we add all functions to this record as described above.
Next we add a function to the operations record that tests whether a certain object is in a residue class.
gap> ResidueClassOps.\in := function ( element, class )
> if IsInt( element ) then
> return (element mod class.modulus = class.representative);
> else
> return false;
> fi;
> end;;
Finally we add a function to compute the intersection of two residue classes.
gap> ResidueClassOps.Intersection := function ( R, S )
> local I, # intersection of R and S, result
> gcd; # gcd of the moduli
> if IsResidueClass( R ) then
> if IsResidueClass( S ) then
> gcd := GcdInt( R.modulus, S.modulus );
> if R.representative mod gcd
> <> S.representative mod gcd
> then
> I := [];
> else
> I := ResidueClass(
> ChineseRem(
> [ R.modulus, S.modulus ] ,
> [ R.representative, S.representative ]),
> Lcm( R.modulus, S.modulus ) );
> fi;
> else
> I := DomainOps.Intersection( R, S );
> fi;
> else
> I := DomainOps.Intersection( R, S );
> fi;
> return I;
> end;;
There is one further thing that we have to do. When Group is called
with a single argument that is a domain, it assumes that you want to
create a new group such that there is a bijection between the original
domain and the new group. This is not what we want here. We want that
in this case we get the cyclic group that is generated by the single
residue class. (This overloading of Group is probably a mistake, but
so is the overloading of residue classes, which are both group elements
and domains.) The following definition solves this problem.
gap> ResidueClassOps.Group := function ( R )
> return ResidueClassesOps.Group( ResidueClasses, [R], R^0 );
> end;;
This concludes our example. There are however several further things
that you could do. One is to add functions for the quotient, the
modulus, etc. Another is to fix the functions so that they do not hang
if asked for the residue class group mod 1. Also you might try to
implement residue class rings analogous to residue class groups. Finally
it might be worthwhile to improve the speed of the multiplication of
prime residue classes. This can be done by doing some precomputation in
ResidueClass and adding some information to the residue class record
for prime residue classes (Mon85).
GAP 3.4.4