Euclidean Ring Interface
If a ring provides a meaningful Euclidean structure such that a useful Euclidean remainder can be computed practically, various additional functionality is provided by AbstractAlgebra.jl for those rings. This functionality depends on the following functions existing. An implementation must provide divrem
, and the remaining are optional as generic fallbacks exist.
divrem
— Methoddivrem(f::T, g::T) where T <: RingElem
Return a pair q, r
consisting of the Euclidean quotient and remainder of by . A DivideError
should be thrown if is zero.
mod
— Methodmod(f::T, g::T) where T <: RingElem
Return the Euclidean remainder of by . A DivideError
should be thrown if is zero.
div
— Methoddiv(f::T, g::T) where T <: RingElem
Return the Euclidean quotient of by . A DivideError
should be thrown if is zero.
mulmod
— Methodmulmod(f::T, g::T, m::T) where T <: RingElem
Return mod(f*g, m)
but possibly computed more efficiently.
powermod
— Methodpowermod(f::T, e::Int, m::T) where T <: RingElem
Return mod(f^e, m)
but possibly computed more efficiently.
invmod
— Methodinvmod(f::T, m::T) where T <: RingElem
Return an inverse of modulo , meaning that isone(mod(invmod(f,m)*f,m))
returns true
.
If such an inverse doesn't exist, a NotInvertibleError
should be thrown.
divides
— Methoddivides(f::T, g::T) where T <: RingElem
Return a pair, flag, q
, where flag
is set to true
if divides , in which case q
is set to the quotient, or flag
is set to false
and q
is undefined.
is_divisible_by
— Methodis_divisible_by(x::T, y::T) where T <: RingElem
Check if x
is divisible by y
, i.e. if for some .
is_associated
— Methodis_associated(x::T, y::T) where T <: RingElem
Check if x
and y
are associated, i.e. if x
is a unit times y
.
remove
— Methodremove(f::T, p::T) where T <: RingElem
Return a pair v, q
where is the highest power of dividing and is the cofactor after is divided by this power.
See also valuation
, which only returns the valuation.
valuation
— Methodvaluation(f::T, p::T) where T <: RingElem
Return v
where is the highest power of dividing .
See also remove
.
gcd
— Methodgcd(a::T, b::T) where T <: RingElem
Return a greatest common divisor of and , i.e., an element which is a common divisor of and , and with the property that any other common divisor of and divides .
gcd
— Methodgcd(f::T, g::T, hs::T...) where T <: RingElem
Return a greatest common divisor of , and the elements in hs
.
gcd
— Methodgcd(fs::AbstractArray{<:T}) where T <: RingElem
Return a greatest common divisor of the elements in fs
. Requires that fs
is not empty.
lcm
— Methodlcm(f::T, g::T) where T <: RingElem
Return a least common multiple of and , i.e., an element which is a common multiple of and , and with the property that any other common multiple of and is a multiple of .
lcm
— Methodlcm(f::T, g::T, hs::T...) where T <: RingElem
Return a least common multiple of , and the elements in hs
.
lcm
— Methodlcm(fs::AbstractArray{<:T}) where T <: RingElem
Return a least common multiple of the elements in fs
. Requires that fs
is not empty.
gcdx
— Methodgcdx(f::T, g::T) where T <: RingElem
Return a triple d, s, t
such that and , with loosely reduced modulo and loosely reduced modulo .
gcdinv
— Methodgcdinv(f::T, g::T) where T <: RingElem
Return a tuple d, s
such that and . Note that iff is invertible modulo , in which case .
crt
— Methodcrt(r1::T, m1::T, r2::T, m2::T; check::Bool=true) where T <: RingElement
Return an element congruent to modulo and modulo . If check = true
and no solution exists, an error is thrown.
If T
is a fixed precision integer type (like Int
), the result will be correct if abs(ri) <= abs(mi)
and abs(m1 * m2) < typemax(T)
.
crt
— Methodcrt(r::Vector{T}, m::Vector{T}; check::Bool=true) where T <: RingElement
Return an element congruent to modulo for each .
crt_with_lcm
— Methodcrt_with_lcm(r1::T, m1::T, r2::T, m2::T; check::Bool=true) where T <: RingElement
Return a tuple consisting of an element congruent to modulo and modulo and the least common multiple of and . If check = true
and no solution exists, an error is thrown.
crt_with_lcm
— Methodcrt_with_lcm(r::Vector{T}, m::Vector{T}; check::Bool=true) where T <: RingElement
Return a tuple consisting of an element congruent to modulo for each and the least common multiple of the .
coprime_base
— Functioncoprime_base(S::Vector{RingElement}) -> Vector{RingElement}
Returns a coprime base for , i.e. the resulting array contains pairwise coprime objects that multiplicatively generate the same set as the input array.
coprime_base(A::Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}
coprime_base(A::Vector{AbsSimpleNumFieldOrderElem}) -> Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}
A coprime base for the (principal) ideals in , i.e. the returned array generated multiplicatively the same ideals as the input and are pairwise coprime.
coprime_base_push!
— Functioncoprime_base_push!(S::Vector{RingElem}, a::RingElem) -> Vector{RingElem}
Given an array of coprime elements, insert a new element, that is, find a coprime base for push(S, a)
.