Elements of Residue Class Rings

Creation

One(R) : RngIntRes -> RngIntResElt

Identity(R) : RngIntRes -> RngIntResElt

Zero(R) : RngIntRes -> RngIntResElt

Representative(R) : RngIntRes -> RngIntResElt

These generic functions create 1, 1, 0, and 0 respectively, in any Z/mZ.

elt< R | k > : RngIntRes, RngIntElt -> RngIntResElt

Create the residue class containing the integer k in residue class ring R.

R ! k : RngIntRes, RngIntElt -> RngIntResElt

Create the residue class containing k in the residue class ring R. Here k is allowed to be either an integer, or an element of the finite field F_p in the case R = Z/pZ, or an element of S = Z/nZ for a multiple or divisor n of m (with R = Z/mZ).

Random(R) : RngIntRes -> RngIntResElt

Create a "random" residue class in R.

Arithmetic Operators

+ n : RngIntResElt -> RngIntResElt

- n : RngIntResElt -> RngIntResElt

m + n : RngIntResElt, RngIntResElt -> RngIntResElt

m - n : RngIntResElt, RngIntResElt -> RngIntResElt

m * n : RngIntResElt, RngIntResElt -> RngIntResElt

n ^ k : RngIntResElt, RngIntResElt -> RngIntResElt

m / n : RngIntResElt, RngIntResElt -> RngIntResElt

m div n : RngIntResElt, RngIntResElt -> RngIntResElt

m +:= n : RngIntResElt, RngIntResElt -> RngIntResElt

m -:= n : RngIntResElt, RngIntResElt -> RngIntResElt

m *:= n : RngIntResElt, RngIntResElt -> RngIntResElt

m /:= n : RngIntResElt, RngIntResElt -> RngIntResElt

m ^:= k : RngIntResElt, RngIntResElt -> RngIntResElt

Equality and Membership

m eq n : RngIntResElt, RngIntResElt -> BoolElt

m ne n : RngIntResElt, RngIntResElt -> BoolElt

n in R : RngIntResElt, Rng -> BoolElt

n notin R : RngIntResElt, Rng -> BoolElt

Parent and Category

Parent(n) : RngIntResElt -> RngIntRes

Category(n) : RngIntResElt -> Cat

Predicates on Ring Elements

IsZero(n) : RngIntResElt -> BoolElt

IsOne(n) : RngIntResElt -> BoolElt

IsMinusOne(n) : RngIntResElt -> BoolElt

IsNilpotent(n) : RngIntResElt -> BoolElt

IsIdempotent(n) : RngIntResElt -> BoolElt

IsUnit(n) : RngIntResElt -> BoolElt

IsZeroDivisor(n) : RngIntResElt -> BoolElt

IsRegular(n) : RngIntRes -> BoolElt

IsIrreducible(n) : RngIntResElt -> BoolElt

IsPrime(n) : RngIntResElt -> BoolElt

Solving Equations over Z/mZ

Solution(a, b) : RngIntResElt, RngIntResElt -> RngIntResElt

Given elements a and b of Z/mZ, return a solution x to the linear congruence a.x=b ∈Z/mZ. An error is signalled if no solution exists.

IsSquare(n) : RngIntResElt -> BoolElt, RngIntResElt

    Factorization: [<RngIntElt, RngIntElt>] Default: [ ]

Given an element n∈Z/mZ this function returns true if there exists a∈Z/mZ such that a²=n∈Z/mZ, false otherwise. If n is a square, a square root a is also returned. If m is large and its prime factorization is known, the computation may be speeded up by assigning the factorization sequence for m to the optional argument Factorization.

Sqrt(a) : RngIntResElt -> RngIntResElt

SquareRoot(a) : RngIntResElt -> RngIntResElt

    Factorization: [<RngIntElt, RngIntElt>] Default: [ ]

Given an element a of the ring Z/mZ, this function returns an element b of Z/mZ such that b²=a∈Z/mZ, if such an element exists, and an error otherwise. If m is large and its prime factorization is known, the computation may be speeded up by assigning the factorization sequence for m to the optional argument Factorization.

AllSquareRoots(a) : RngIntResElt -> [ RngIntResElt ]

AllSqrts(a) : RngIntResElt -> [ RngIntResElt ]

    Factorization: [<RngIntElt, RngIntElt>] Default: [ ]

Return a sequence containing all square roots of the element a in a residue class ring Z/mZ. If the modulus m is large and its prime factorization is known, the computation may be speeded up by assigning the factorization sequence for m to the optional argument Factorization.

> R := ResidueClassRing(2340);
Residue class ring of integers modulo 2340
> x := R!1404;
> sqrts := AllSquareRoots(x);
> sqrts;
[ 78, 312, 468, 702, 858, 1092, 1248, 1482, 1638, 
  1872, 2028, 2262 ]
> [ y^2 : y in sqrts ];
[ 1404, 1404, 1404, 1404, 1404, 1404, 1404, 1404, 
  1404, 1404, 1404, 1404 ]