incorrect answer: CRT(Mod{2^64}(0), Mod{2^128-1}(1))

[StefanKarpinski]

Here's the incorrect computation:

julia> using Mods

julia> m = UInt128(2)^64
0x00000000000000010000000000000000

julia> n = UInt128(2)^128-1
0xffffffffffffffffffffffffffffffff

julia> a = Mod{m}(0)
Mod{18446744073709551616}(0)

julia> b = Mod{n}(1)
Mod{340282366920938463463374607431768211455}(0)

julia> CRT(a, b)
0

That's obviously incorrect since 0 ≠ 1 (mod n). The correct answer is 2^128.

[scheinerman]

Well, this is an interesting problem that I'm not sure how to solve. The issue is already apparent when you define b = Mod{n}(1) and the result is Mod{n}(0). (So I don't think this has anything to do with CRT.)

A while back I looked into having the modulus be any sort of integer, including a BigInt, but as I recall one can't use a BigInt as a type parameter. Has that changed?

@StefanKarpinski Is the solution to restrict the modulus to be an Int (or an Int128)? I'm not sure how to proceed.

[StefanKarpinski]

No, having non-primitive (immutable really) types as type parameters is unlikely to happen. Consider: if you have a = big(123) and b = big(123) are Mod{a} and Mod{b} the same type or not? What if you do Base.GMP.flipsign!(a, -1)? After that you have a == -123 and b == 123 still.

I guess the issue here is doing arithmetic with the modulus and having that arithmetic overflow? The best that can be done is probably either what you're doing (correct answer modulo the type), or a checked arithmetic error. Having a version of CRT solving that doesn't involve type parameters would also be handy, but this package may not be the place for it.