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 of Euclidean rings with type EuclideanRingResidueRingElem{T} or in the case of residue rings that are known to be fields, EuclideanRingResidueFieldElem{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 EuclideanRingResidueRing{T} and those of residue fields have type EuclideanRingResidueField{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.

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)$ together with the canonical projection. 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.

source

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.

source

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);

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 R modulo x^3 + 3*x + 1, Map: R -> S)

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.

source

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);

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 R 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.

source

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);

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.

source

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);

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.

source

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.

source

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);

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

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

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