|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Alexander Konovalov.
##
## 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/nZ(epsilon)$,
## where epsilon is the primitive root of unity of degree m (not depending
## on n).
## The following approach was used to construct such rings. First we create
## a ring of integral cyclotomics in the m-th cyclotomic field. Then we
## construct from its elements a new ring, defining operations modulo n.
## Thus, elements of the ring $Z/nz(epsilon)$ internally are represented
## as cyclotomic integers.
##
#############################################################################
#
# RingOfIntegralCyclotomics( F )
#
# Let F be a cyclotomic field. This function returns the ring of integral
# cyclotomics of the field F
#
InstallGlobalFunction( RingOfIntegralCyclotomics,
function( F )
local R;
if not IsCyclotomicField( F ) then
Error("RingOfIntegralCyclotomics : an argument is not cyclotomic field !");
fi;
R := RingWithOne( E( Conductor( F ) ) );
SetIsRingOfIntegralCyclotomics( R, true );
SetName( R, Concatenation( "(RingInt(CF(", String(Conductor(F)), ")))" ) );
return R;
end );
#############################################################################
#
# ZmodnZepsObj( Fam, celt )
#
# This function takes a cyclotomic element celt and creates an object in a
# family Fam, internally represented by this cyclotomic
#
InstallGlobalFunction( ZmodnZepsObj,
function( Fam, celt )
local n , m, coeffs, elt;
m := Fam!.degree;
n := Fam!.modulus;
# we find coefficients of celt in the m-th Zumbroich basis
# this guarantee the canonical form of an element from Z_m(eps)
coeffs := CoeffsCyc(celt, m);
if ForAny(coeffs, x -> not IsInt(x)) then
Error("ZmodnZepsObj : cyclotomic is not integral !!!");
fi;
# now we reduce coefficients modulo n
coeffs := List(coeffs, x -> x mod n);
elt := coeffs * List( [1..m], j -> E(m)^(j-1) );
return Objectify( NewType( Fam, IsZmodnZepsObj and IsZmodnZepsRep ),
[ elt ] );
end );
#############################################################################
#
# ZmodnZeps( n, m)
#
# This function returns the ring $Z/nZ(epsilon)$, where n is a positive
# integer and epsilon is a primitive root of unity of degree m.
# Alternatively, the same result may me obtained using the command
# RingInt(CF(m)) mod n
# since below we install special method for \mod operation for this case
#
InstallGlobalFunction( ZmodnZeps,
function( n, m )
local F, R;
if not IsPosInt( m ) then
Error( "<m> must be a positive integer" );
fi;
if not IsPosInt( n ) then
Error( "<n> must be a positive integer" );
fi;
# Construct the family of element objects of our ring.
F := NewFamily( Concatenation( "Zmod", String(n), "Z(", String(m), ")" ),
IsZmodnZepsObj );
# Install the data.
F!.modulus := n;
F!.degree := m;
# Make the domain.
R := RingWithOneByGenerators( [ ZmodnZepsObj( F, E(m) ) ] );
SetIsWholeFamily( R, true );
SetName( R, Concatenation( "(RingInt(CF(", String(m), ")) mod ",
String(n), ")" ) );
# Return the ring.
return R;
end );
#############################################################################
#
# PrintObj( R )
#
# If R is the ring $Z/nZ(epsilon)$, where epsilon^m=1, then it will be
# printed in the following form:
# RingInt(CF(m)) mod n
#
InstallMethod( PrintObj,
"zmodnze : for full collection Z/nZ(m)",
[ CategoryCollections( IsZmodnZepsObj ) and IsWholeFamily ],
function( R )
local F, m, n;
F := ElementsFamily( FamilyObj(R) );
n := F!.modulus;
m := F!.degree;
Print( Concatenation( "(RingInt(CF(", String(m), ")) mod ",
String(n), ")" ) );
end );
#############################################################################
#
# PrintObj( x )
#
# If x is an element of the ring $Z/nZ(epsilon)$, where epsilon^m=1, and celt
# is its underlying cyclotomic element (thus, its internal representation),
# then x will be printed in the following form:
# ( celt mod n )
#
InstallMethod( PrintObj,
"zmodnze : for element in Z/nZ(m) (ZmodnZepsRep)",
[ IsZmodnZepsObj and IsZmodnZepsRep ],
function( x )
Print( "( ", x![1], " mod ", FamilyObj(x)!.modulus, " )" );
end );
#############################################################################
#
# x=y
#
# x equal y iff corresponding underlying cyclotomics are equal, since
# their canonical form is uniquely determined by ZmodnZepsObj
#
InstallMethod( \=,
"zmodnze : for two elements in Z/nZ(m) (ZmodnZepsRep)",
IsIdenticalObj,
[ IsZmodnZepsObj and IsZmodnZepsRep,
IsZmodnZepsObj and IsZmodnZepsRep ],
function( x, y )
return x![1] = y![1]; end );
#############################################################################
#
# x < y
#
# this is just extending of relation "<" implemented in GAP for
# cyclotomics. Thus, x < y iff the same relation holds for underlying
# cyclotomics, since their canonical form is uniquely determined by
# ZmodnZepsObj
#
InstallMethod( \<,
"zmodnze : for two elements in Z/nZ(m) (ZmodnZepsRep)",
IsIdenticalObj,
[ IsZmodnZepsObj and IsZmodnZepsRep,
IsZmodnZepsObj and IsZmodnZepsRep ],
function( x, y )
return x![1] < y![1];
end );
#############################################################################
#
# x+y
#
# x and y in Z/nZ(m)
# x in Z/nZ(m), y Cyclotomic
# x Cyclotomic, y in Z/nZ(m)
#
# These operations are implemented via appropriate operations over
# (underlying) cyclotomics and then 'objectifying' the result
#
InstallMethod( \+,
"zmodnze : for two elements in Z/nZ(m) (ZmodnZepsRep)",
IsIdenticalObj,
[ IsZmodnZepsObj and IsZmodnZepsRep,
IsZmodnZepsObj and IsZmodnZepsRep ],
function( x, y )
return ZmodnZepsObj( FamilyObj( x ), x![1] + y![1] );
end );
InstallMethod( \+,
"zmodnze : for element in Z/nZ(m) (ZmodnZepsRep) and cyclotomic",
[ IsZmodnZepsObj and IsZmodnZepsRep, IsCyclotomic ],
function( x, y )
return ZmodnZepsObj( FamilyObj( x ), x![1] + y );
end );
InstallMethod( \+,
"zmodnze : for cyclotomic and element in Z/nZ(m) (ZmodnZepsRep)",
[ IsCyclotomic, IsZmodnZepsObj and IsZmodnZepsRep ],
function( x, y )
return ZmodnZepsObj( FamilyObj( y ), x + y![1] );
end );
#############################################################################
#
# x * y
# x Cyclotomic , y in Z/nZ(m)
# x in Z/nZ(m) , y Cyclotomic
# x in Z/nZ(m) , y in Z/nZ
# x in Z/nZ , y in Z/nZ(m)
# x in Z/nZ(m) , y in Z/nZ(m)
#
# These operations are implemented via appropriate operations over
# (underlying) cyclotomics and then 'objectifying' the result
#
InstallMethod( \*,
"zmodnze : for cyclotomic x and element y in Z/nZ(m) (ZmodnZepsRep)",
[ IsCyclotomic,
IsZmodnZepsObj and IsZmodnZepsRep ],
function( x, y )
return ZmodnZepsObj( FamilyObj( y ), x * y![1] );
end );
InstallMethod( \*,
"zmodnze : for element x in Z/nZ(m) (ZmodnZepsRep) and cyclotomic y",
[ IsZmodnZepsObj and IsZmodnZepsRep,
IsCyclotomic],
function( x, y )
return ZmodnZepsObj( FamilyObj( x ), x![1] * y );
end );
InstallMethod( \*,
"zmodnze : for element x in Z/nZ(m) and y in Z/nZ",
[ IsZmodnZepsObj and IsZmodnZepsRep,
IsZmodnZObj and IsModulusRep],
function( x, y )
return ZmodnZepsObj( FamilyObj( x ), x![1] * Int(y) );
end );
InstallMethod( \*,
"zmodnze : for element x in Z/nZ and y in Z/nZ(m)",
[ IsZmodnZObj and IsModulusRep,
IsZmodnZepsObj and IsZmodnZepsRep],
function( x, y )
return ZmodnZepsObj( FamilyObj( y ), Int(x) * y![1] );
end );
InstallMethod( \*,
"zmodnze : for two elements in Z/nZ(m) (ZmodnZepsRep)",
IsIdenticalObj,
[ IsZmodnZepsObj and IsZmodnZepsRep,
IsZmodnZepsObj and IsZmodnZepsRep ],
function( x, y )
return ZmodnZepsObj( FamilyObj( x ), x![1] * y![1] );
end );
#############################################################################
#
# Zero
#
InstallMethod( ZeroOp,
"zmodnze : for element in Z/nZ(m) (ZmodnZepsRep)",
[ IsZmodnZepsObj ],
x -> ZmodnZepsObj( FamilyObj( x ), 0 ) );
#############################################################################
#
# One
#
InstallMethod( OneOp,
"zmodnze : for element in Z/nZ(m) (ZmodnZepsRep)",
[ IsZmodnZepsObj ],
elm -> ZmodnZepsObj( FamilyObj( elm ), 1 ) );
#############################################################################
#
# -x
#
InstallMethod( AdditiveInverseOp,
"zmodnze : for element in Z/nZ(m) (ZmodnZepsRep)",
[ IsZmodnZepsObj and IsZmodnZepsRep ],
x -> ZmodnZepsObj( FamilyObj( x ), AdditiveInverse( x![1] ) ) );
#############################################################################
#
# Cyclotomic
#
# returns an underlying cyclotomic element
#
InstallMethod( Cyclotomic,
"zmodnze : for element in Z/nZ(m) (ZmodnZepsRep)",
[ IsZmodnZepsObj and IsZmodnZepsRep ],
z -> z![1] );
#############################################################################
#
# mod
#
# Creates the ring Z/nZ(m) from the ring Z/nZ
#
InstallMethod( \mod,
"zmodnze : for RingOfIntegralCyclotomics and a positive integer",
[ IsRingOfIntegralCyclotomics,
IsPosRat and IsInt ],
function( R, n )
return ZmodnZeps( n, Conductor(GeneratorsOfRingWithOne(R)[1]) );
end );
#############################################################################
#
# Size of Z/nZ(m) is equal to n^Phi(m)
#
InstallMethod( Size,
"zmodnze : for full ring Z/nZ(m)",
[ CategoryCollections( IsZmodnZepsObj ) and IsWholeFamily ],
R -> ElementsFamily(FamilyObj(R))!.modulus^
Phi(ElementsFamily(FamilyObj(R))!.degree));
#############################################################################
#
# IsFinite = true
#
InstallTrueMethod( IsFinite,
CategoryCollections( IsZmodnZepsObj ) and IsDomain );
#############################################################################
#
# Random
#
InstallMethodWithRandomSource( Random,
"for a random source and the full collection Z/nZ(m)",
[ IsRandomSource, CategoryCollections( IsZmodnZepsObj ) and IsWholeFamily ],
function(rs, R)
local m, n, coeffs, elt;
m:=FamilyObj(One(R))!.degree;
n:=FamilyObj(One(R))!.modulus;
coeffs := List([1..m], x -> Random(rs, 0, n-1));
elt := coeffs * List( [1..m], j -> E(m)^(j-1) );
return ZmodnZepsObj( FamilyObj(One(R)) , elt );
end );
#############################################################################
#
# Enumerator
#
InstallMethod( Enumerator,
"zmodnze : for full collection Z/nZ(m)",
[ CategoryCollections( IsZmodnZepsObj ) and IsWholeFamily ],
function( R )
local F, m, n, x, j;
F:= ElementsFamily( FamilyObj(R) );
m:=FamilyObj(One(R))!.degree;
n:=FamilyObj(One(R))!.modulus;
return List( Enumerator( (Integers mod n)^Phi(m) ),
x -> ZmodnZepsObj(F, List(x,Int) *
List( [1..Phi(m)], j -> E(m)^(j-1) ) ) );
end );
#############################################################################
#
# IsUnit( R, elm )
#
# checks whether the element is a unit, building the list of its powers
# 1. <elm>^<deg>=1 => <elm>^(-1)=<elm>^<deg-1>
# 2. <elm>^<deg>=0 => <elm> is not a unit
# 3. <elm>^<deg>=<elm>^<deg+C> => <elm> is not a unit
#
InstallMethod( IsUnit,
"zmodnze : for element in Z/nZ(m) (ZModnZepsRep) with given ring",
[ CategoryCollections( IsZmodnZepsObj ) and IsWholeFamily and IsRing,
IsZmodnZepsObj and IsZmodnZepsRep ],
function( R, elm )
local pow, powers;
if HasUnits(R) then
return elm in Units(R);
fi;
powers:=[]; # to store powers of elm
pow:=elm;
while true do
if pow*elm=One(elm) then
return true;
elif IsZero(pow) or (pow in powers) then
return false;
fi;
Add(powers,pow);
pow:=pow*elm;
od;
end );
#############################################################################
#
# IsUnit( elm )
#
# checks whether the element is a unit, building the list of its powers
# 1. <elm>^<deg>=1 => <elm>^(-1)=<elm>^<deg-1>
# 2. <elm>^<deg>=0 => <elm> is not a unit
# 3. <elm>^<deg>=<elm>^<deg+C> => <elm> is not a unit
#
InstallOtherMethod( IsUnit,
"zmodnze : for element in Z/nZ(m) (ZModnZepsRep) without given ring",
[ IsZmodnZepsObj and IsZmodnZepsRep ],
function( elm )
local pow, powers;
powers:=[]; # to store powers of elm
pow:=elm;
while true do
if pow*elm=One(elm) then
return true;
elif IsZero(pow) or (pow in powers) then
return false;
fi;
Add(powers,pow);
pow:=pow*elm;
od;
end );
#############################################################################
#
# x^-1
# calculates the inverse element building the list of its powers
#
InstallMethod( InverseOp,
"zmodnze : for element in Z/nZ(m) (ZModnZepsRep)",
[ IsZmodnZepsObj and IsZmodnZepsRep ],
function( elm )
local pow, powers;
powers:=[]; # to store powers of elm
pow:=elm;
while true do
if pow*elm=One(elm) then
return pow;
elif IsZero(pow) or (pow in powers) then
return fail;
fi;
Add(powers,pow);
pow:=pow*elm;
od;
end );
#############################################################################
#
# Units
#
# now simply generates the group using all units.
# TODO: Improve by minimizing the list of generators
#
InstallMethod( Units,
"zmodnze : for full ring Z/nZ(m)",
[ CategoryCollections( IsZmodnZepsObj ) and IsWholeFamily and IsRing ],
function( R )
return Group( Filtered(AsList(R), IsUnit ) );
end );
[ Dauer der Verarbeitung: 0.44 Sekunden
(vorverarbeitet)
]
|
