non coprime moduli are not supported by CRT for IntegerMod_int
We have
sage: crt([6,0],[10,4])
16
However:
sage: mod(6,10).crt(mod(0,4))
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call last)
/usr/local/SageMath.94/local/lib/python3.9/site-packages/sage/rings/finite_rings/integer_mod.pyx in sage.rings.finite_rings.integer_mod.IntegerMod_int.__crt (build/cythonized/sage/rings/finite_rings/integer_mod.c:26973)()
2464 try:
-> 2465 x = (other.ivalue - self.ivalue % other.__modulus.int32) * mod_inverse_int(self.__modulus.int32, other.__modulus.int32)
2466 lift.set_from_int( x * self.__modulus.int32 + self.ivalue )
/usr/local/SageMath.94/local/lib/python3.9/site-packages/sage/rings/finite_rings/integer_mod.pyx in sage.rings.finite_rings.integer_mod.mod_inverse_int (build/cythonized/sage/rings/finite_rings/integer_mod.c:31277)()
3045 next_t = last_t - q * t
-> 3046 raise ZeroDivisionError(f"inverse of Mod({x}, {n}) does not exist")
3047
ZeroDivisionError: inverse of Mod(10, 4) does not exist
During handling of the above exception, another exception occurred:
ZeroDivisionError Traceback (most recent call last)
<ipython-input-102-08ac2f32f772> in <module>
----> 1 mod(Integer(6),Integer(10)).crt(mod(Integer(0),Integer(4)))
/usr/local/SageMath.94/local/lib/python3.9/site-packages/sage/rings/finite_rings/integer_mod.pyx in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.crt (build/cythonized/sage/rings/finite_rings/integer_mod.c:19297)()
1643 new_modulus = self.__modulus.int64 * other.__modulus.int64
1644 if new_modulus < INTEGER_MOD_INT32_LIMIT:
-> 1645 return self.__crt(other)
1646
1647 elif new_modulus < INTEGER_MOD_INT64_LIMIT:
/usr/local/SageMath.94/local/lib/python3.9/site-packages/sage/rings/finite_rings/integer_mod.pyx in sage.rings.finite_rings.integer_mod.IntegerMod_int.__crt (build/cythonized/sage/rings/finite_rings/integer_mod.c:27037)()
2467 return lift
2468 except ZeroDivisionError:
-> 2469 raise ZeroDivisionError("moduli must be coprime")
2470
2471
ZeroDivisionError: moduli must be coprime
What's the deal here? Why unlike the first crt
, the second crt
(from sage.rings.finite_rings.integer_mod_ring
) insists on moduli being coprime? Could this restriction be eliminated?
I've submitted this RFE in ticket https://github.com/sagemath/sage/issu...