Generic Chinese Remainder Theorem

[ambiso]

Sage has a crt and CRT_list function which work for essentially any ring.

AbstractAlgebra has a crt function, which it documents to be extendable by Singular, Nemo and Hecke.

However, I couldn't find an implementation of crt for Polynomial Rings in Nemo. Yet a completely generic version of it "just works" :sparkles: with them.

What do you think about adding a function similar to this one to AbstractAlgebra?

function crt(a, b, m, n)
    g, α, β = gcdx(m, n)
    q, r = divrem(b - a, g)
    if r != zero(a)
        throw(DomainError("No solution to crt problem since gcd($m,$n) does not divide $a-$b"))
    end
    mod(a + q*α*m, lcm(m, n))
end

function crt(a::Array, n::Array)
    x = a[1]
    m = n[1]
    for (n, a) in zip(n, a)
        x = crt(x, a, m, n)
        m = lcm(m, n)
    end
    mod(x, m)
end

The implementation above is entirely based upon sage's: crt CRT_list

Please note that sage is distributed under GPLv2.

[wbhart]

Thanks for the question, but this is my personal repository for AbstractAlgebra. You would be better opening the ticket on the official repository at https://github.com/Nemocas/AbstractAlgebra.jl

You will get more attention on the issue over there.

Unfortunately GitHub has my repository as the top one, rather than the official one, and we don't know how to change it. Sorry for the confusion.

Regarding the GPL, although our projects are overall distributed under the GPL, the individual Julia files are BSD licensed. That means we can't use Sage code in AbstractAlgebra.

We also don't allow unicode in library code, but these are minor points, especially given that rewriting Open Source code in another language using the same algorithm, but different expression doesn't violate anyone's copyright. One can't have a copyright on a well-known algorithm.

[ambiso]

Thank you :)

[ambiso]

May I link your comment in the issue I'm creating on the main repository regarding copyright?

[wbhart]

Yes of course. I am one of the maintainers, I just want others to be able to comment.