#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Thomas Breuer.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains methods for the elements of the rings $Z / n Z$
## in their representation via the residue modulo $n$.
## This residue is always assumed to be in the range $[ 0, 1 ..., n-1 ]$.
##
## Each ring $\Z / n \Z$ contains the whole elements family if $n$ is not a
## prime, and is embedded into the family of finite field elements of
## characteristic $n$ otherwise.
##
## If $n$ is not a prime then an external representation of elements is
## defined. For the element $k + n \Z$, it is the representative $k$,
## chosen such that $0 \leq k \leq n - 1$.
##
## The ordering of elements for nonprime $n$ is defined by the ordering of
## the representatives.
## For primes smaller than `MAXSIZE_GF_INTERNAL', the ordering of the
## internal finite field elements must be respected, for larger primes
## again the ordering of representatives is chosen.
##
#T for small residue class rings, avoid constructing new objects by
#T keeping an elements list, and change the constructor such that the
#T object in question is just fetched
#T (check performance for matrices over Z/4Z, say)
#############################################################################
##
#R IsModulusRep( <obj> )
##
## Objects in this representation are defined by a single data entry, an
## integer at first position.
##
if IsHPCGAP then
DeclareRepresentation( "IsModulusRep", IsReadOnlyPositionalObjectRep, [ 1 ] );
else
DeclareRepresentation( "IsModulusRep", IsPositionalObjectRep, [ 1 ] );
fi;
#############################################################################
##
## 1. The elements
##
#############################################################################
##
#M ZmodnZObj( <Fam>, <residue> )
#M ZmodnZObj( <residue>, <modulus> )
##
InstallMethod( ZmodnZObj,
"for family of elements in Z/nZ (nonprime), and integer",
[ IsZmodnZObjNonprimeFamily, IsInt ],
function( Fam, residue )
return Objectify( Fam!.typeOfZmodnZObj,
[ residue mod Fam!.Characteristic ] );
end );
InstallOtherMethod( ZmodnZObj,
"for family of elements in Z/nZ (nonprime), and rational",
[ IsZmodnZObjNonprimeFamily, IsRat ],
function( Fam, val )
local m;
m:= Fam!.Characteristic;
if GcdInt( DenominatorRat( val ), m ) <> 1 then
return fail;
fi;
return Objectify( Fam!.typeOfZmodnZObj, [ val mod m ] );
end );
InstallOtherMethod( ZmodnZObj,
"for family of FFE elements, and integer",
[ IsFFEFamily, IsInt ],
function( Fam, residue )
local p;
p:= Fam!.Characteristic;
if not IsBound( Fam!.typeOfZmodnZObj ) then
# Store the type for the representation of prime field elements
# via residues.
Fam!.typeOfZmodnZObj:= NewType( Fam,
IsZmodpZObjSmall and IsModulusRep );
fi;
return Objectify( Fam!.typeOfZmodnZObj, [ residue mod p ] );
end );
InstallMethod( ZmodnZObj,
"for a positive integer, and an integer -- check small primes",
[ IsInt, IsPosInt ],
function( residue, n )
if n in PRIMES_COMPACT_FIELDS then
return residue*Z(n)^0;
fi;
return ZmodnZObj( ElementsFamily( FamilyObj( ZmodnZ( n ) ) ), residue );
end );
#############################################################################
##
#M ObjByExtRep( <Fam>, <residue> )
##
## Note that finite field elements do not have an external representation.
##
InstallMethod( ObjByExtRep,
"for family of elements in Z/nZ (nonprime), and integer",
[ IsZmodnZObjNonprimeFamily, IsInt ],
function( Fam, residue )
return ZmodnZObj( Fam, residue );
end );
#############################################################################
##
#M ExtRepOfObj( <obj> )
##
InstallMethod( ExtRepOfObj,
"for element in Z/nZ (ModulusRep, nonprime)",
[ IsZmodnZObjNonprime and IsModulusRep ],
obj -> obj![1] );
#############################################################################
##
#M PrintObj( <obj> ) . . . . . . . . . . . for element in Z/nZ (ModulusRep)
##
InstallMethod( PrintObj,
"for element in Z/nZ (ModulusRep)",
IsZmodnZObjNonprimeFamily,
[ IsZmodnZObj and IsModulusRep ],
function( x )
Print( "ZmodnZObj( ", x![1], ", ", FamilyObj( x )!.Characteristic, " )" );
end );
InstallMethod( PrintObj,
"for element in Z/pZ (ModulusRep)",
[ IsZmodpZObj and IsModulusRep ],
function( x )
Print( "ZmodpZObj( ", x![1], ", ", FamilyObj( x )!.Characteristic, " )" );
end );
InstallMethod( String,
"for element in Z/nZ (ModulusRep)",
IsZmodnZObjNonprimeFamily,
[ IsZmodnZObj and IsModulusRep ],
function( x )
return Concatenation( "ZmodnZObj(", String(x![1]), ",",
String(FamilyObj( x )!.Characteristic), ")" );
end );
InstallMethod( String,
"for element in Z/pZ (ModulusRep)",
[ IsZmodpZObj and IsModulusRep ],
function( x )
return Concatenation( "ZmodpZObj(", String(x![1]), ",",
String(FamilyObj( x )!.Characteristic), ")" );
end );
#############################################################################
##
#M \=( <x>, <y> )
#M \<( <x>, <y> )
##
InstallMethod( \=,
"for two elements in Z/nZ (ModulusRep)",
IsIdenticalObj,
[ IsZmodnZObj and IsModulusRep, IsZmodnZObj and IsModulusRep ],
function( x, y ) return x![1] = y![1]; end );
InstallMethod( \=,
"for element in Z/pZ (ModulusRep) and internal FFE",
IsIdenticalObj,
[ IsZmodpZObj and IsModulusRep, IsFFE and IsInternalRep ],
function( x, y )
return DegreeFFE( y ) = 1 and x![1] = IntFFE( y );
end );
InstallMethod( \=,
"for internal FFE and element in Z/pZ (ModulusRep)",
IsIdenticalObj,
[ IsFFE and IsInternalRep, IsZmodpZObj and IsModulusRep ],
function( x, y )
return DegreeFFE( x ) = 1 and y![1] = IntFFE( x );
end );
InstallMethod( \<,
"for two elements in Z/nZ (ModulusRep, nonprime)",
IsIdenticalObj,
[ IsZmodnZObjNonprime and IsModulusRep,
IsZmodnZObjNonprime and IsModulusRep ],
function( x, y ) return x![1] < y![1]; end );
InstallMethod( \<,
"for two elements in Z/pZ (ModulusRep, large)",
IsIdenticalObj,
[ IsZmodpZObjLarge and IsModulusRep,
IsZmodpZObjLarge and IsModulusRep ],
function( x, y ) return x![1] < y![1]; end );
InstallMethod( \<,
"for two elements in Z/pZ (ModulusRep, small)",
IsIdenticalObj,
[ IsZmodpZObjSmall and IsModulusRep,
IsZmodpZObjSmall and IsModulusRep ],
function( x, y )
local p, r; # characteristic and primitive root
if x![1] = 0 then
return y![1] <> 0;
elif y![1] = 0 then
return false;
fi;
p:= Characteristic( x );
r:= PrimitiveRootMod( p );
return LogMod( x![1], r, p ) < LogMod( y![1], r, p );
end );
InstallMethod( \<,
"for element in Z/pZ (ModulusRep) and internal FFE",
IsIdenticalObj,
[ IsZmodpZObjSmall and IsModulusRep, IsFFE and IsInternalRep ],
function( x, y )
return x![1] * One( Z( Characteristic( x ) ) ) < y;
end );
InstallMethod( \<,
"for internal FFE and element in Z/pZ (ModulusRep)",
IsIdenticalObj,
[ IsFFE and IsInternalRep, IsZmodpZObjSmall and IsModulusRep ],
function( x, y )
return x < y![1] * One( Z( Characteristic( y ) ) );
end );
#############################################################################
##
#M \+( <x>, <y> )
#M \-( <x>, <y> )
#M \*( <x>, <y> )
#M \/( <x>, <y> )
#M \^( <x>, <n> )
##
## The result of an arithmetic operation of
## - two `ZmodnZObj' is again a `ZmodnZObj',
## - a `ZmodnZObj' and a rational with acceptable denominator
## is a `ZmodnZObj',
## - a `ZmodpZObj' and an internal FFE in the same characteristic
## is an internal FFE.
##
InstallMethod( \+,
"for two elements in Z/nZ (ModulusRep)",
IsIdenticalObj,
[ IsZmodnZObj and IsModulusRep, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] + y![1] );
end );
InstallMethod( \+,
"for element in Z/nZ (ModulusRep) and integer",
[ IsZmodnZObj and IsModulusRep, IsInt ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] + y );
end );
InstallMethod( \+,
"for integer and element in Z/nZ (ModulusRep)",
[ IsInt, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( y ), x + y![1] );
end );
InstallMethod( \+,
"for element in Z/nZ (ModulusRep) and rational",
[ IsZmodnZObj and IsModulusRep, IsRat ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] + y );
end );
InstallMethod( \+,
"for rational and element in Z/nZ (ModulusRep)",
[ IsRat, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( y ), x + y![1] );
end );
InstallMethod( \+,
"for element in Z/pZ (ModulusRep) and internal FFE",
IsIdenticalObj,
[ IsZmodpZObjSmall and IsModulusRep, IsFFE and IsInternalRep ],
function( x, y ) return x![1] + y; end );
InstallMethod( \+,
"for internal FFE and element in Z/pZ (ModulusRep)",
IsIdenticalObj,
[ IsFFE and IsInternalRep, IsZmodpZObjSmall and IsModulusRep ],
function( x, y ) return x + y![1]; end );
InstallMethod( \-,
"for two elements in Z/nZ (ModulusRep)",
IsIdenticalObj,
[ IsZmodnZObj and IsModulusRep, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] - y![1] );
end );
InstallMethod( \-,
"for element in Z/nZ (ModulusRep) and integer",
[ IsZmodnZObj and IsModulusRep, IsInt ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] - y );
end );
InstallMethod( \-,
"for integer and element in Z/nZ (ModulusRep)",
[ IsInt, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( y ), x - y![1] );
end );
InstallMethod( \-,
"for element in Z/nZ (ModulusRep) and rational",
[ IsZmodnZObj and IsModulusRep, IsRat ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] - y );
end );
InstallMethod( \-,
"for rational and element in Z/nZ (ModulusRep)",
[ IsRat, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( y ), x - y![1] );
end );
InstallMethod( \-,
"for element in Z/pZ (ModulusRep) and internal FFE",
IsIdenticalObj,
[ IsZmodpZObjSmall and IsModulusRep, IsFFE and IsInternalRep ],
function( x, y ) return x![1] - y; end );
InstallMethod( \-,
"for internal FFE and element in Z/pZ (ModulusRep)",
IsIdenticalObj,
[ IsFFE and IsInternalRep, IsZmodpZObjSmall and IsModulusRep ],
function( x, y ) return x - y![1]; end );
InstallMethod( \*,
"for two elements in Z/nZ (ModulusRep)",
IsIdenticalObj,
[ IsZmodnZObj and IsModulusRep, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] * y![1] );
end );
InstallMethod( \*,
"for element in Z/nZ (ModulusRep) and integer",
[ IsZmodnZObj and IsModulusRep, IsInt ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] * y );
end );
InstallMethod( \*,
"for integer and element in Z/nZ (ModulusRep)",
[ IsInt, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( y ), x * y![1] );
end );
InstallMethod( \*,
"for element in Z/nZ (ModulusRep) and rational",
[ IsZmodnZObj and IsModulusRep, IsRat ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] * y );
end );
InstallMethod( \*,
"for rational and element in Z/nZ (ModulusRep)",
[ IsRat, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( y ), x * y![1] );
end );
InstallMethod( \*,
"for element in Z/pZ (ModulusRep) and internal FFE",
IsIdenticalObj,
[ IsZmodpZObjSmall and IsModulusRep, IsFFE and IsInternalRep ],
function( x, y ) return x![1] * y; end );
InstallMethod( \*,
"for internal FFE and element in Z/pZ (ModulusRep)",
IsIdenticalObj,
[ IsFFE and IsInternalRep, IsZmodpZObjSmall and IsModulusRep ],
function( x, y ) return x * y![1]; end );
InstallMethod( \/,
"for two elements in Z/nZ (ModulusRep)",
IsIdenticalObj,
[ IsZmodnZObj and IsModulusRep, IsZmodnZObj and IsModulusRep ],
function( x, y )
local Fam, q;
Fam := FamilyObj( x );
q := QuotientMod( Integers, x![1], y![1],
Fam!.Characteristic );
if q = fail then
Error("invalid division");
fi;
return ZmodnZObj( Fam, q );
end );
InstallMethod( \/,
"for element in Z/nZ (ModulusRep) and integer",
[ IsZmodnZObj and IsModulusRep, IsInt ],
function( x, y )
local Fam, q;
Fam := FamilyObj( x );
q := QuotientMod( Integers, x![1], y,
Fam!.Characteristic );
if q = fail then
Error("invalid division");
fi;
return ZmodnZObj( Fam, q );
end );
InstallMethod( \/,
"for integer and element in Z/nZ (ModulusRep)",
[ IsInt, IsZmodnZObj and IsModulusRep ],
function( x, y )
local Fam, q;
Fam := FamilyObj( y );
q := QuotientMod( Integers, x, y![1],
Fam!.Characteristic );
if q = fail then
Error("invalid division");
fi;
return ZmodnZObj( Fam, q );
end );
InstallMethod( \/,
"for element in Z/nZ (ModulusRep) and rational",
[ IsZmodnZObj and IsModulusRep, IsRat ],
function( x, y )
return ZmodnZObj( FamilyObj( x ), x![1] / y );
end );
InstallMethod( \/,
"for rational and element in Z/nZ (ModulusRep)",
[ IsRat, IsZmodnZObj and IsModulusRep ],
function( x, y )
return ZmodnZObj( FamilyObj( y ), x / y![1] );
end );
InstallMethod( \/,
"for element in Z/pZ (ModulusRep) and internal FFE",
IsIdenticalObj,
[ IsZmodpZObjSmall and IsModulusRep, IsFFE and IsInternalRep ],
function( x, y ) return x![1] / y; end );
InstallMethod( \/,
"for internal FFE and element in Z/pZ (ModulusRep)",
IsIdenticalObj,
[ IsFFE and IsInternalRep, IsZmodpZObjSmall and IsModulusRep ],
function( x, y ) return x / y![1]; end );
InstallMethod( \^,
"for element in Z/nZ (ModulusRep), and integer",
[ IsZmodnZObj and IsModulusRep, IsInt ],
function( x, n )
local Fam;
Fam := FamilyObj( x );
return ZmodnZObj( Fam,
PowerModInt( x![1], n, Fam!.Characteristic ) );
end );
#############################################################################
##
#M ZeroOp( <elm> ) . . . . . . . . . . . . . . . . . . . . for `IsZmodnZObj'
##
InstallMethod( ZeroOp,
"for element in Z/nZ (ModulusRep)",
[ IsZmodnZObj ],
elm -> ZmodnZObj( FamilyObj( elm ), 0 ) );
#############################################################################
##
#M AdditiveInverseOp( <elm> ) . . . . . . . . . . . . . . for `IsZmodnZObj'
##
InstallMethod( AdditiveInverseOp,
"for element in Z/nZ (ModulusRep)",
[ IsZmodnZObj and IsModulusRep ],
elm -> ZmodnZObj( FamilyObj( elm ), AdditiveInverse( elm![1] ) ) );
#############################################################################
##
#M OneOp( <elm> ) . . . . . . . . . . . . . . . . . . . . for `IsZmodnZObj'
##
InstallMethod( OneOp,
"for element in Z/nZ (ModulusRep)",
[ IsZmodnZObj ],
elm -> ZmodnZObj( FamilyObj( elm ), 1 ) );
#############################################################################
##
#M InverseOp( <elm> ) . . . . . . . . . . . . . . . . . . for `IsZmodnZObj'
##
InstallMethod( InverseOp,
"for element in Z/nZ (ModulusRep)",
[ IsZmodnZObj and IsModulusRep ],
function( elm )
local fam, inv;
fam:= FamilyObj( elm );
inv:= QuotientMod( Integers, 1, elm![1], fam!.Characteristic );
if inv <> fail then
inv:= ZmodnZObj( fam, inv );
fi;
return inv;
end );
#############################################################################
##
#M Order( <obj> ) . . . . . . . . . . . . . . . . . . . . for `IsZmodpZObj'
##
InstallMethod( Order,
"for element in Z/nZ (ModulusRep)",
[ IsZmodnZObj and IsModulusRep ],
function( elm )
local ord;
ord := OrderMod( elm![1], FamilyObj( elm )!.Characteristic );
if ord = 0 then
Error( "<obj> is not invertible" );
fi;
return ord;
end );
#############################################################################
##
#M DegreeFFE( <obj> ) . . . . . . . . . . . . . . . . . . for `IsZmodpZObj'
##
InstallMethod( DegreeFFE,
"for element in Z/pZ (ModulusRep)",
[ IsZmodpZObj and IsModulusRep ],
z -> 1 );
#############################################################################
##
#M LogFFE( <n>, <r> ) . . . . . . . . . . . . . . . . . . for `IsZmodpZObj'
##
InstallMethod( LogFFE,
"for two elements in Z/pZ (ModulusRep)",
IsIdenticalObj,
[ IsZmodpZObj and IsModulusRep, IsZmodpZObj and IsModulusRep ],
function( n, r )
return LogMod( n![1], r![1], Characteristic( n ) );
end );
#############################################################################
##
#M RootFFE( <z>, <k> ) . . . . . . . . . . . . . . . . . . for `IsZmodpZObj'
##
InstallOtherMethod(RootFFE,"for modulus rep, using RootMod",true,
[IsPosInt,IsZmodpZObj and IsModulusRep,IsPosInt],
function( A, z, k )
local r,fam;
fam:=FamilyObj(z);
if A<>fam!.Characteristic then
TryNextMethod();
fi;
if k=1 or z![1]=0 or z![1]=1 then return z;fi;
r:=RootMod(z![1],k,A);
if r=fail then return r;fi;
return ZmodnZObj(fam,r);
end );
InstallOtherMethod(RootFFE,"for modulus rep",true,
[IsZmodpZObj and IsModulusRep,IsPosInt],
function(z,k)
return RootFFE(FamilyObj(z)!.Characteristic,z,k);
end);
#############################################################################
##
#M Int( <obj> ) . . . . . . . . . . . . . . . . . . . . . for `IsZmodnZObj'
##
InstallMethod( Int,
"for element in Z/nZ (ModulusRep)",
[ IsZmodnZObj and IsModulusRep ],
z -> z![1] );
#############################################################################
##
#M IntFFE( <obj> ) . . . . . . . . . . . . . . . . . . . for `IsZmodnZObj'
##
InstallMethod(IntFFE,
[IsZmodpZObj and IsModulusRep],
x->x![1]);
#############################################################################
##
#M IntFFESymm( <obj> ) . . . . . . . . . . . . . . . . . . . for `IsZmodnZObj'
##
InstallOtherMethod(IntFFESymm,"Z/nZ (ModulusRep)",
[IsZmodnZObj and IsModulusRep],
function(z)
local n;
n:=Characteristic( FamilyObj(z) );
if 2*z![1]>n then
return z![1]-n;
else
return z![1];
fi;
end);
#############################################################################
##
#M Z(p) ... return a primitive root
##
InstallMethod(ZOp,
[IsPosInt],
function(p)
local f;
if p <= MAXSIZE_GF_INTERNAL then
TryNextMethod(); # should never happen
fi;
if not IsProbablyPrimeInt(p) then
TryNextMethod();
fi;
f := FFEFamily(p);
if not IsBound(f!.primitiveRootModP) then
f!.primitiveRootModP := PrimitiveRootMod(p);
fi;
return ZmodnZObj(f!.primitiveRootModP,p);
end);
#############################################################################
##
#M EuclideanDegree( <R>, <n> )
##
## For an overview on the theory of euclidean rings which are not domains,
## see Pierre Samuel, "About Euclidean rings", J. Algebra, 1971 vol. 19 pp. 282-301.
##
https://doi.org/10.1016/0021-8693(71)90110-4
InstallMethod( EuclideanDegree,
"for Z/nZ and an element in Z/nZ",
IsCollsElms,
[ IsZmodnZObjNonprimeCollection and IsWholeFamily and IsRing, IsZmodnZObj and IsModulusR
ep ],
function ( R, n )
return GcdInt( n![1], Characteristic( n ) );
end );
#############################################################################
##
#M QuotientRemainder( <R>, <n>, <m> )
##
InstallMethod( QuotientRemainder,
"for Z/nZ and two elements in Z/nZ",
IsCollsElmsElms,
[ IsZmodnZObjNonprimeCollection and IsWholeFamily and IsRing,
IsZmodnZObj and IsModulusRep, IsZmodnZObj and IsModulusRep ],
function ( R, n, m )
local u, s, q, r;
u := StandardAssociateUnit(R, m);
s := u * m; # the standard associate of m
q := QuoInt(n![1], s![1]);
r := n![1] - q * s![1];
return [ ZmodnZObj( FamilyObj( n ), (q * u![1]) mod Characteristic(R) ),
ZmodnZObj( FamilyObj( n ), r ) ];
end );
#############################################################################
##
#M Quotient( <R>, <n>, <m> ) . . . . . . . . . . . . . . . for `IsZmodnZObj'
##
InstallMethod( Quotient,
"for Z/nZ and two elements in Z/nZ",
IsCollsElmsElms,
[ IsZmodnZObjNonprimeCollection and IsWholeFamily and IsRing,
IsZmodnZObj and IsModulusRep, IsZmodnZObj and IsModulusRep ],
function ( R, x, y )
local Fam, q;
Fam := FamilyObj( x );
q := QuotientMod( Integers, x![1], y![1],
Fam!.Characteristic );
if q = fail then
return fail;
fi;
return ZmodnZObj( Fam, q );
end );
#############################################################################
##
#M StandardAssociate( <r> )
##
InstallMethod( StandardAssociate,
"for full ring Z/nZ and an element in Z/nZ",
IsCollsElms,
[ IsZmodnZObjNonprimeCollection and IsWholeFamily and IsRing, IsZmodnZObj and IsModulusRep ],
function ( R, r )
local m, n;
m := Characteristic( r );
n := GcdInt( r![1], m );
return ZmodnZObj( FamilyObj( r ), n );
end );
#############################################################################
##
#M StandardAssociateUnit( <r> )
##
InstallMethod( StandardAssociateUnit,
"for full ring Z/nZ and an element in Z/nZ",
IsCollsElms,
[ IsZmodnZObjNonprimeCollection and IsWholeFamily and IsRing, IsZmodnZObj and IsModulusRep ],
function ( R, r )
local m, n, u, pd, p, d, x, residues, moduli;
# zero is associated to itself, so return identity
if r![1] = 0 then
return ZmodnZObj( FamilyObj( r ), 1 );
fi;
m := Characteristic( r );
# divide input by its standard associate
n := r![1] / GcdInt( r![1], m );
# we really need the "inverse" of n, i.e., a unit u such that r*u is
# equal to the standard associate. If n is a unit (i.e., coprime to the
# modulus m), we can invert it and use that as u:
if GcdInt( n, m ) = 1 then
u := (1 / n) mod m;
return ZmodnZObj( FamilyObj( r ), u );
fi;
# otherwise, first factor the modulus m into a product of prime powers,
# m = p_1^{d_1} \cdots p_k^{d_k}. Then compute the StandardAssociateUnit
# modulo each p_i^{d_i}; then finally use the Chinese Remainder Theorem
# to combine these back together.
residues := [];
moduli := [];
for pd in Collected(Factors(Integers, m)) do
p := pd[1];
d := pd[2];
pd := p^d;
if n mod p = 0 then
# if n is divisible by p, then in fact r![1] is divisible by p^d,
# i.e., it is 0 mod p^d, and we can choose 1 as the
# StandardAssociateUnit (mod p^d)
x := 1;
else
# if n is not divisible by p, we can invert it modulo p^d to get
# the StandardAssociateUnit (mod p^d)
x := 1 / n mod pd;
fi;
Add( residues, x );
Add( moduli, pd );
od;
u := ChineseRem( moduli, residues );
return ZmodnZObj( FamilyObj( r ), u );
end );
#############################################################################
##
#M IsAssociated( <R>, <n>, <m> )
##
InstallMethod( IsAssociated,
"for Z/nZ and two elements in Z/nZ",
IsCollsElmsElms,
[ IsZmodnZObjNonprimeCollection and IsWholeFamily and IsRing,
IsZmodnZObj and IsModulusRep, IsZmodnZObj and IsModulusRep ],
function ( R, n, m )
R := Characteristic( n );
return GcdInt( n![1], R ) = GcdInt( m![1], R );
end );
## 2. The collections
##
#############################################################################
##
#M InverseOp( <mat> ) . . . . . . . . . . . . for ordinary matrix over Z/nZ
#M InverseSameMutability( <mat> ) . . . . . . for ordinary matrix over Z/nZ
##
## For a nonprime integer $n$, the residue class ring $\Z/n\Z$ has zero
## divisors, so the standard algorithm to invert a matrix over $\Z/n\Z$
## cannot be applied.
##
#T The method below should of course be replaced by a method that uses
#T inversion modulo the maximal prime powers dividing the modulus,
#T this ``brute force method'' is only preliminary!
##
InstallMethod( InverseOp,
"for an ordinary matrix over a ring Z/nZ",
[ IsMatrix and IsOrdinaryMatrix and IsZmodnZObjNonprimeCollColl ],
function( mat )
local one;
one:= One( mat[1][1] );
mat:= InverseOp( List( mat, row -> List( row, Int ) ) );
if mat <> fail then
mat:= mat * one;
fi;
if not IsMatrix( mat ) then
mat:= fail;
fi;
return mat;
end );
InstallMethod( InverseSameMutability,
"for an ordinary matrix over a ring Z/nZ",
[ IsMatrix and IsOrdinaryMatrix and IsZmodnZObjNonprimeCollColl ],
function( mat )
local inv, row;
inv:= InverseOp( mat );
if inv <> fail then
if not IsMutable( mat ) then
MakeImmutable( inv );
elif not IsMutable( mat[1] ) then
for row in inv do
MakeImmutable( row );
od;
fi;
fi;
return inv;
end );
InstallMethod( TriangulizeMat,
"for a mutable ordinary matrix over a ring Z/nZ",
[ IsMatrix and IsMutable and IsOrdinaryMatrix
and IsZmodnZObjNonprimeCollColl ],
function( mat )
local imat, i;
imat:= List( mat, row -> List( row, Int ) );
TriangulizeMat( imat );
imat:= imat * One( mat[1][1] );
for i in [ 1 .. Length( mat ) ] do
mat[i]:= imat[i];
od;
end );
#############################################################################
##
#M ViewObj( <R> ) . . . . . . . . . . . . . . . . method for full ring Z/nZ
#M PrintObj( <R> ) . . . . . . . . . . . . . . . . method for full ring Z/nZ
##
InstallMethod( ViewObj,
"for full ring Z/nZ",
[ IsZmodnZObjNonprimeCollection and IsWholeFamily ], SUM_FLAGS,
function( obj )
Print( "(Integers mod ", Size( obj ), ")" );
end );
InstallMethod( PrintObj,
"for full ring Z/nZ",
[ IsZmodnZObjNonprimeCollection and IsWholeFamily ], SUM_FLAGS,
function( obj )
Print( "(Integers mod ", Size( obj ), ")" );
end );
#############################################################################
##
#M AsSSortedList( <R> ) . . . . . . . . . . . . set of elements of Z mod n Z
#M AsList( <R> ) . . . . . . . . . . . . . . . set of elements of Z mod n Z
##
InstallMethod( AsList,
"for full ring Z/nZ",
[ IsZmodnZObjNonprimeCollection and IsWholeFamily ],
{} -> RankFilter( IsRing ),
AsSSortedList );
InstallMethod( AsSSortedList,
"for full ring Z/nZ",
[ IsZmodnZObjNonprimeCollection and IsWholeFamily ],
{} -> RankFilter( IsRing ),
function( R )
local F;
F:= ElementsFamily( FamilyObj( R ) );
F:= List( [ 0 .. Size( R ) - 1 ], x -> ZmodnZObj( F, x ) );
SetIsSSortedList( F, true );
return F;
end );
#############################################################################
##
#M Random( <R> ) . . . . . . . . . . . . . . . . . method for full ring Z/nZ
##
InstallMethodWithRandomSource(Random,
"for a random source and full ring Z/nZ",
[ IsRandomSource, IsZmodnZObjNonprimeCollection and IsWholeFamily ],
{} -> RankFilter( IsRing ),
{ rs, R } -> ZmodnZObj( ElementsFamily( FamilyObj( R ) ),
Random( rs, 0, Size( R ) - 1 ) ) );
#############################################################################
##
#M IsIntegralRing( <obj> ) . . . . . . . . . . method for subrings of Z/nZ
##
InstallImmediateMethod( IsIntegralRing,
IsZmodnZObjNonprimeCollection and IsRing, 0,
ReturnFalse );
#############################################################################
##
#M IsUnit( <obj> ) . . . . . . . . . . . . . . . . . . . for `IsZmodpZObj'
##
InstallMethod( IsUnit,
"for element in Z/nZ (ModulusRep)",
IsCollsElms,
[ IsZmodnZObjNonprimeCollection and IsWholeFamily and IsRing, IsZmodnZObj and IsModulusRep ],
function( R, elm )
return GcdInt( elm![1], FamilyObj( elm )!.Characteristic ) = 1;
end );
#############################################################################
##
#M Units( <R> ) . . . . . . . . . . . . . . . . . method for full ring Z/nZ
##
InstallMethod( Units,
"for full ring Z/nZ",
[ IsZmodnZObjNonprimeCollection and IsWholeFamily and IsRing ],
function( R )
local G, gens;
gens := GeneratorsPrimeResidues( Size( R ) ).generators;
if not IsEmpty( gens ) and gens[ 1 ] = 1 then
gens := gens{ [ 2 .. Length( gens ) ] };
fi;
gens := Flat( gens ) * One( R );
G := GroupByGenerators( gens, One( R ) );
SetIsAbelian( G, true );
SetSize( G, Product( List( gens, Order ) ) );
SetIsHandledByNiceMonomorphism(G,true);
return G;
end );
#############################################################################
##
#M <res> in <G> . . . . . . . . . . . for cyclic prime residue class groups
##
InstallMethod( \in,
"for subgroups of Z/p^aZ, p<>2",
IsElmsColls,
[ IsZmodnZObjNonprime, IsGroup and IsZmodnZObjNonprimeCollection ],
function( res, G )
local m;
m := FamilyObj( res )!.Characteristic;
res := Int( res );
if GcdInt( res, m ) <> 1 then
return false;
elif IsEvenInt(m) or not IsPrimePowerInt( m ) then
TryNextMethod();
fi;
return LogMod( res, PrimitiveRootMod( m ), m ) mod
( Phi( m ) / Size( G ) ) = 0;
end );
#############################################################################
##
#F EnumeratorOfZmodnZ( <R> ). . . . . . . . . . . . . enumerator for Z / n Z
#M Enumerator( <R> ) . . . . . . . . . . . . . . . . enumerator for Z / n Z
##
BindGlobal( "ElementNumber_ZmodnZ", function( enum, nr )
if nr > enum!.size then
Error( "<enum>[", nr, "] must have an assigned value" );
fi;
return Objectify( enum!.type, [ nr - 1 ] );
end );
BindGlobal( "NumberElement_ZmodnZ", function( enum, elm )
if IsCollsElms( FamilyObj( enum ), FamilyObj( elm ) ) then
return elm![1] + 1;
fi;
return fail;
end );
InstallGlobalFunction( EnumeratorOfZmodnZ, function( R )
local enum;
enum:= EnumeratorByFunctions( R, rec(
ElementNumber := ElementNumber_ZmodnZ,
NumberElement := NumberElement_ZmodnZ,
size:= Size( R ),
type:= ElementsFamily( FamilyObj( R ) )!.typeOfZmodnZObj ) );
SetIsSSortedList( enum, true );
return enum;
end );
InstallMethod( Enumerator,
"for full ring Z/nZ",
[ IsZmodnZObjNonprimeCollection and IsWholeFamily ], SUM_FLAGS,
EnumeratorOfZmodnZ );
#############################################################################
##
#M SquareRoots( <F>, <obj> )
##
## (is used in the implementation of Dixon's algorithm ...)
##
InstallMethod( SquareRoots,
"for prime field and object in Z/pZ",
IsCollsElms,
[ IsField and IsPrimeField, IsZmodpZObj and IsModulusRep ],
function( F, obj )
F:= FamilyObj( obj );
return List( RootsMod( obj![1], 2, F!.Characteristic ),
x -> ZmodnZObj( F, x ) );
end );
#############################################################################
##
#F ZmodpZ( <p> ) . . . . . . . . . . . . . . . construct `Integers mod <p>'
#F ZmodpZNC( <p> ) . . . . . . . . . . . . . . construct `Integers mod <p>'
##
InstallGlobalFunction( ZmodpZ, function( p )
if not IsPrimeInt( p ) then
Error( "<p> must be a prime" );
fi;
return ZmodpZNC( AbsInt( p ) );
end );
InstallGlobalFunction( ZmodpZNC, p -> GET_FROM_SORTED_CACHE( Z_MOD_NZ, p, function( )
local F;
# Get the family of element objects of our ring.
F:= FFEFamily( p );
# Make the domain.
F:= FieldOverItselfByGenerators( [ ZmodnZObj( F, 1 ) ] );
SetIsPrimeField( F, true );
SetIsWholeFamily( F, false );
# Return the field.
return F;
end ) );
#############################################################################
##
#F ZmodnZ( <n> ) . . . . . . . . . . . . . . . construct `Integers mod <n>'
##
InstallGlobalFunction( ZmodnZ, function( n )
local F, R;
if not IsInt( n ) then
Error( "<n> must be an integer" );
elif n = 0 then
return Integers;
elif n < 0 then
n := -n;
fi;
if IsPrimeInt( n ) then
return ZmodpZNC( n );
fi;
return GET_FROM_SORTED_CACHE( Z_MOD_NZ, n, function( )
# Construct the family of element objects of our ring.
F:= NewFamily( Concatenation( "Zmod", String( n ) ),
IsZmodnZObj,
IsZmodnZObjNonprime and CanEasilySortElements
and IsNoImmediateMethodsObject,
CanEasilySortElements);
# Install the data.
SetCharacteristic(F,n);
# Store the objects type.
F!.typeOfZmodnZObj:= NewType( F, IsZmodnZObjNonprime and IsModulusRep );
# as n is no prime, the family is no UFD, so we don't add IsUFDFamily as a filter
# Make the domain.
R:= RingWithOneByGenerators( [ ZmodnZObj( F, 1 ) ] );
SetIsWholeFamily( R, true );
SetZero(F,Zero(R));
SetOne(F,One(R));
SetSize(R,n);
# Return the ring.
return R;
end );
end );
#############################################################################
##
#M \mod( Integers, <n> )
##
InstallMethod( \mod,
"for `Integers', and integer",
[ IsIntegers, IsInt ],
function( Integers, n ) return ZmodnZ( n ); end );
#############################################################################
##
#M ModulusOfZmodnZObj( <obj> )
##
## For an element <obj> in a residue class ring of integers modulo $n$
## (see~"IsZmodnZObj"), `ModulusOfZmodnZObj' returns the positive integer
## $n$.
##
InstallMethod( ModulusOfZmodnZObj,
"for element in Z/nZ (nonprime)",
[ IsZmodnZObjNonprime ],
res -> FamilyObj( res )!.Characteristic );
InstallMethod( ModulusOfZmodnZObj,
"for element in Z/pZ (prime)",
[ IsZmodpZObj ],
Characteristic );
InstallOtherMethod( ModulusOfZmodnZObj,
"for FFE",
[ IsFFE ],
function( ffe )
if DegreeFFE( ffe ) = 1 then
return Characteristic( ffe );
else
return fail;
fi;
end );
#############################################################################
##
#M DefaultRingByGenerators( <zmodnzcoll> )
##
InstallMethod( DefaultRingByGenerators,
"for a collection over a ring Z/nZ",
[ IsZmodnZObjNonprimeCollection ],
C -> ZmodnZ( Characteristic( Representative( C ) ) ) );
#############################################################################
##
#M DefaultFieldOfMatrixGroup( <zmodnz-mat-grp> )
##
## Is it possible to avoid this very special method?
## In fact the whole stuff in the library is not very clean,
## as the ``generic'' method for matrix groups claims to be allowed to
## call `Field'.
## The bad name of the function (`DefaultFieldOfMatrixGroup') may be the
## reason for this bad behaviour.
## Do we need to distinguish matrix groups over fields and rings that aren't
## fields, and change the generic `DefaultFieldOfMatrixGroup' method
## accordingly?
##
InstallMethod( DefaultFieldOfMatrixGroup,
"for a matrix group over a ring Z/nZ",
[ IsMatrixGroup and IsZmodnZObjNonprimeCollCollColl ],
G -> ZmodnZ( Characteristic( Representative( G )[1,1] ) ) );
#############################################################################
##
#M AsInternalFFE( <zmodpzobj> )
##
## A ZmodpZ object can be a finite field element, but is never equal to
## an internal FFE, so this method just returns fail
##
InstallMethod(AsInternalFFE, [IsZmodpZObj], ReturnFail);
