Quelle zmodnz.gi Sprache: unbekannt

#############################################################################
##
## 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 IsModulusRep ],
 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( ) . . . . . . . . . . . . . . . construct `Integers mod '
#F ZmodpZNC( ) . . . . . . . . . . . . . . construct `Integers mod '
##
InstallGlobalFunction( ZmodpZ, function( p )
 if not IsPrimeInt( p ) then
 Error( " 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);

Quelle zmodnz.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.42 Sekunden (vorverarbeitet) ]