non coprime moduli are not supported by CRT for IntegerMod_int

asked 2021-09-06 00:05:30 +0200

Max Alekseyev gravatar image

updated 2021-09-06 00:24:43 +0200

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?

edit retag flag offensive close merge delete

Comments

I've submitted this RFE in ticket https://trac.sagemath.org/ticket/32487

Max Alekseyev gravatar imageMax Alekseyev ( 2021-09-08 00:19:27 +0200 )edit