Introduction

Chinese Remainder Theorem

The Chinese Remainder Theorem is a method to solve systems of linear congruences. We can apply it whenever we are able to perform division with a remainder. Given residues r1, ..., rn and pairwise coprime moduli m1, ... mn we return an x so that x = ri mod mi for all i. This solution is unique modulo N = lcm(m1, ... mn).

If we need to apply the chinese remainder theorem repeatedly for a fixed set of (coprime) moduli, we can precompute all the necessary information and save it in a prepared environment.

crt_env — Method

crt_env(p::Vector{T}) -> crt_env{T}

Given coprime moduli in some euclidean ring (ZZ, zzModRingElem_poly, ZZRingElem_mod_poly), prepare data for fast application of the chinese remainder theorem for those moduli.

source

Any ring that has a divrem method has access to some crt methods provided by the euclidean_interface:

crt — Method

crt(r1::T, m1::T, r2::T, m2::T; check::Bool=true) where T <: RingElement

Return an element congruent to $r_1$ modulo $m_1$ and $r_2$ modulo $m_2$. 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).

source

crt — Method

crt(r::Vector{T}, m::Vector{T}; check::Bool=true) where T <: RingElement

Return an element congruent to $r_i$ modulo $m_i$ for each $i$.

source

crt — Method

crt{T}(b::Vector{T}, a::crt_env{T}) -> T

Given values in $b$ and the environment prepared by crt\_env, return the unique (modulo the product) solution to $x \equiv b_i \bmod p_i$.

source

crt_with_lcm — Method

crt_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 $r_1$ modulo $m_1$ and $r_2$ modulo $m_2$ and the least common multiple of $m_1$ and $m_2$. If check = true and no solution exists, an error is thrown.

source

crt_with_lcm — Method

crt_with_lcm(r::Vector{T}, m::Vector{T}; check::Bool=true) where T <: RingElement

Return a tuple consisting of an element congruent to $r_i$ modulo $m_i$ for each $i$ and the least common multiple of the $m_i$.

source

We often want to apply the chinese remainder theorem to the coefficients of polynomials, or to the entries of a matrix, with respect to the underlying ring. For this we use the induce_crt method:

induce_crt — Function

induce_crt(a::ZZPolyRingElem, p::ZZRingElem, b::ZZPolyRingElem, q::ZZRingElem, signed::Bool = false) -> ZZPolyRingElem

Given integral polynomials $a$ and $b$ as well as coprime integer moduli $p$ and $q$, find $f = a \bmod p$ and $f=b \bmod q$. If signed is set, the symmetric representative is used, the positive one otherwise.

source

induce_crt — Method

induce_crt(L::Vector{PolyRingElem}, c::crt_env{ZZRingElem}) -> ZZPolyRingElem

Given ZZRingElem_poly polynomials $L[i]$ and a crt\_env, apply the crt function to each coefficient resulting in a polynomial $f = L[i] \bmod p[i]$.

source

induce_crt — Method

induce_crt(L::Vector{MatElem}, c::crt_env{ZZRingElem}) -> ZZMatrix

Given matrices $L[i]$ and a crt\_env, apply the crt function to each coefficient resulting in a matrix $M = L[i] \bmod p[i]$.

source

<!– crtinv(a::T, c::crtenv{T}) where T –> <!– There is also modular_env –> <!– No docs for crtsigned –> <!– crtsigned(b::Vector{ZZRingElem}, a::crt_env{ZZRingElem}) –>

We also have variants for number fields that can take as arguments residues along with respective ideals of the corresponding ring of integers. These are calculated using a decomposition into idempotents.

crt — Method

crt(r1::AbsSimpleNumFieldOrderElem, i1::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, r2::AbsSimpleNumFieldOrderElem, i2::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}) -> AbsSimpleNumFieldOrderElem

Find $x$ such that $x \equiv r_1 \bmod i_1$ and $x \equiv r_2 \bmod i_2$ using idempotents.

source

induce_crt — Method

induce_crt(a::Generic.Poly{AbsSimpleNumFieldElem}, p::ZZRingElem, b::Generic.Poly{AbsSimpleNumFieldElem}, q::ZZRingElem) -> Generic.Poly{AbsSimpleNumFieldElem}, ZZRingElem

Given polynomials $a$ defined modulo $p$ and $b$ modulo $q$, apply the CRT to all coefficients recursively. Implicitly assumes that $a$ and $b$ have integral coefficients (i.e. no denominators).

source

This variant is also supported in the following signatures: crt(r1::Hecke.AlgAssAbsOrdElem, i1::Hecke.AlgAssAbsOrdIdl, r2::Hecke.AlgAssAbsOrdElem, i2::Hecke.AlgAssAbsOrdIdl) crt(r1::Hecke.RelNumFieldOrderElem, i1::Hecke.RelNumFieldOrderIdeal, r2::Hecke.RelNumFieldOrderElem, i2::Hecke.RelNumFieldOrderIdeal) crt(r1::AbsSimpleNumFieldOrderElem, i1::AbsSimpleNumFieldOrderIdeal, r2::AbsSimpleNumFieldOrderElem, i2::AbsSimpleNumFieldOrderIdeal) crt(a::Vector{Hecke.AlgAssAbsOrdElem}, I::Vector{Hecke.AlgAssAbsOrdIdl}) crt(a::Vector{Hecke.RelNumFieldOrderElem}, I::Vector{Hecke.RelNumFieldOrderIdeal}) crt(a::Vector{AbsSimpleNumFieldOrderElem}, I::Vector{AbsSimpleNumFieldOrderIdeal}) crt(a::Vector{ZZRingElem}, I::Vector{Hecke.ZZIdl}) <!– No docs for these –> <!– @docs crt(r1::S, i1::T, r2::S, i2::T) where {S<:Union{Hecke.AlgAssAbsOrdElem, Hecke.RelNumFieldOrderElem, AbsSimpleNumFieldOrderElem}, T<:Union{Hecke.AlgAssAbsOrdIdl, Hecke.RelNumFieldOrderIdeal, AbsSimpleNumFieldOrderIdeal}} crt(a::Vector{S}, I::Vector{T}) where {S<:Union{Hecke.AlgAssAbsOrdElem, Hecke.RelNumFieldOrderElem, AbsSimpleNumFieldOrderElem}, T<:Union{Hecke.AlgAssAbsOrdIdl, Hecke.RelNumFieldOrderIdeal, AbsSimpleNumFieldOrderIdeal}} crt(a::Vector{ZZRingElem}, b::Vector{Hecke.ZZIdl}) –>