Generic residue rings

AbstractAlgebra.jl provides modules, implemented in src/Residue.jl and src/residue_field for residue rings and fields, respectively, over any Euclidean domain (in practice most of the functionality is provided for GCD domains that provide a meaningful GCD function) belonging to the AbstractAlgebra.jl abstract type hierarchy.

Generic residue types

AbstractAlgebra.jl implements generic residue rings with type Generic.ResidueRingElem{T} or in the case of residue rings that are known to be fields, Generic.ResidueFieldElem{T}, where T is the type of elements of the base ring. See the file src/generic/GenericTypes.jl for details.

Parent objects of generic residue ring elements have type Generic.ResidueRing{T} and those of residue fields have type GenericResField{T}.

The defining modulus of the residue ring is stored in the parent object.

Abstract types

All residue element types belong to the abstract type ResElem{T} or ResFieldElem{T} in the case of residue fields, and the residue ring types belong to the abstract type ResidueRing{T} or ResidueField{T} respectively. This enables one to write generic functions that can accept any AbstractAlgebra residue type.

Note

Note that both the generic residue ring type Generic.ResidueRing{T} and the abstract type it belongs to, ResidueRing{T} are both called ResidueRing, and similarly for the residue field types. In each case, the former is a (parameterised) concrete type for a residue ring over a given base ring whose elements have type T. The latter is an abstract type representing all residue ring types in AbstractAlgebra.jl, whether generic or very specialised (e.g. supplied by a C library).

Residue ring constructors

In order to construct residues in AbstractAlgebra.jl, one must first construct the residue ring itself. This is accomplished with one of the following constructors.

residue_ring(R::Ring, m::RingElem; cached::Bool = true)

residue_field(R::Ring, m::RingElem; cached::Bool = true)

Given a base ring R and residue $m$ contained in this ring, return the parent object of the residue ring $R/(m)$. By default the parent object S will depend only on R and m and will be cached. Setting the optional argument cached to false will prevent the parent object S from being cached.

The residue_field constructor does the same thing as the residue_ring constructor, but the resulting object has type belonging to Field rather than Ring, so it can be used anywhere a field is expected in AbstractAlgebra.jl. No check is made for maximality of the ideal generated by $m$.

There are also the following for constructing residue rings and fields.

quo — Method

quo(R::Ring, a::RingElement; cached::Bool = true)

Returns S, f where S = residue_ring(R, a) and f is the projection map from R to S. This map is supplied as a map with section where the section is the lift of an element of the residue field back to the ring R.

quo — Method

quo(::Type{Field}, R::Ring, a::RingElement; cached::Bool = true)

Returns S, f where S = residue_field(R, a) and f is the projection map from R to S. This map is supplied as a map with section where the section is the lift of an element of the residue field back to the ring R.

Here are some examples of creating residue rings and making use of the resulting parent objects to coerce various elements into the residue ring.

Examples

julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)

julia> S = residue_ring(R, x^3 + 3x + 1)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1

julia> f = S()
0

julia> g = S(123)
123

julia> h = S(BigInt(1234))
1234

julia> k = S(x + 1)
x + 1

julia> U, f = quo(R, x^3 + 3x + 1)
(Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1, Map with section with the following data

Domain:
=======
Univariate polynomial ring in x over rationals

Codomain:
========
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1)

julia> U === S
true

All of the examples here are generic residue rings, but specialised implementations of residue rings provided by external modules will also usually provide a residue_ring constructor to allow creation of their residue rings.

Residue constructors

One can use the parent objects of a residue ring to construct residues, as per any ring.

(R::ResidueRing)() # constructs zero
(R::ResidueRing)(c::Integer)
(R::ResidueRing)(c::elem_type(R))
(R::ResidueRing{T})(a::T) where T <: RingElement

Functions for types and parents of residue rings

base_ring(R::ResidueRing)
base_ring(a::ResElem)

Return the base ring over which the ring was constructed.

parent(a::ResElem)

Return the parent of the given residue.

characteristic(R::ResidueRing)

Return the characteristic of the given residue ring. If the characteristic is not known, an exception is raised.

Residue ring functions

Basic functionality

Residue rings implement the Ring interface.

zero(R::NCRing)
one(R::NCRing)
iszero(a::NCRingElement)
isone(a::NCRingElement)

divexact(a::T, b::T) where T <: RingElement
inv(a::T)

The Residue Ring interface is also implemented.

modulus(S::ResidueRing)

data(f::ResElem)
lift(f::ResElem)

Return a lift of the residue to the base ring.

The following functions are also provided for residues.

modulus — Method

modulus(R::ResElem)

Return the modulus $a$ of the residue ring $S = R/(a)$ that the supplied residue $r$ belongs to.

Examples

julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)

julia> S = residue_ring(R, x^3 + 3x + 1)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1

julia> f = S(x + 1)
x + 1

julia> h = zero(S)
0

julia> k = one(S)
1

julia> isone(k)
true

julia> iszero(f)
false

julia> is_unit(f)
true

julia> m = modulus(S)
x^3 + 3*x + 1

julia> d = data(f)
x + 1

julia> U = base_ring(S)
Univariate polynomial ring in x over rationals

julia> V = base_ring(f)
Univariate polynomial ring in x over rationals

julia> T = parent(f)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1

julia> f == deepcopy(f)
true

julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)

Inversion

inv — Method

Base.inv(a::ResElem)

Return the inverse of the element $a$ in the residue ring. If an impossible inverse is encountered, an exception is raised.

Examples

julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)

julia> S = residue_ring(R, x^3 + 3x + 1)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1

julia> f = S(x + 1)
x + 1

julia> g = inv(f)
1//3*x^2 - 1//3*x + 4//3

Greatest common divisor

gcd — Method

gcd(a::ResElem{T}, b::ResElem{T}) where {T <: RingElement}

Return a greatest common divisor of $a$ and $b$ if one exists. This is done by taking the greatest common divisor of the data associated with the supplied residues and taking its greatest common divisor with the modulus.

Examples

julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)

julia> S = residue_ring(R, x^3 + 3x + 1)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1

julia> f = S(x + 1)
x + 1

julia> g = S(x^2 + 2x + 1)
x^2 + 2*x + 1

julia> h = gcd(f, g)
1

Square Root

is_square — Method

is_square(a::ResFieldElem{T}) where T <: Integer

Return true if $a$ is a square.

sqrt — Method

sqrt(a::ResFieldElem{T}; check::Bool=true) where T <: Integer

Return the square root of $a$. By default the function will throw an exception if the input is not square. If check=false this test is omitted.

Examples

julia> R = residue_field(ZZ, 733)
Residue field of Integers modulo 733

julia> a = R(86)
86

julia> is_square(a)
true

julia> sqrt(a)
532

Random generation

Random residues can be generated using rand. The parameters after the residue ring are used to generate elements of the base ring.

rand(R::ResidueRing, v...)

Examples

julia> R = residue_ring(ZZ, 7)
Residue ring of integers modulo 7

julia> f = rand(R, 0:6)
4

julia> S, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)

julia> U = residue_field(S, x^3 + 3x + 1)
Residue field of univariate polynomial ring modulo x^3 + 3*x + 1

julia> g = rand(S, 2:2, -10:10)
-1//4*x^2 - 2//7*x + 1