CRT_vectors does not handle non-coprime moduli

[user202729]

Steps To Reproduce

sage: CRT_vectors([[3, 5], [3, 5]], [4, 6])
ValueError: moduli must be coprime

Expected Behavior

Actual Behavior

Additional Information

Lead to a test failure here https://github.com/sagemath/sage/actions/runs/12390050306/job/34584290514?pr=39153#step:10:8784

sage -t --warn-long 5.0 --random-seed=171635645973753757565886362497935495350 src/sage/schemes/elliptic_curves/ell_point.py
**********************************************************************
File "src/sage/schemes/elliptic_curves/ell_point.py", line 276, in sage.schemes.elliptic_curves.ell_point.?._add_
Failed example:
    R = P + Q
Exception raised:
    Traceback (most recent call last):
      File "/Users/runner/work/sage/sage/src/sage/doctest/forker.py", line 716, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/runner/work/sage/sage/src/sage/doctest/forker.py", line 1137, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.schemes.elliptic_curves.ell_point.?._add_[13]>", line 1, in <module>
        R = P + Q
            ~~^~~
      File "sage/structure/element.pyx", line 1219, in sage.structure.element.Element.__add__
        return (<Element>left)._add_(right)
      File "sage/structure/element.pyx", line 2376, in sage.structure.element.ModuleElement._add_
        cpdef _add_(self, other):
      File "/Users/runner/work/sage/sage/src/sage/schemes/elliptic_curves/ell_point.py", line 344, in _add_
        pt = CRT_vectors([pt, [x2.lift(), y2.lift(), z2.lift()]], [mod, mod_2nd])
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      File "/Users/runner/work/sage/sage/src/sage/arith/misc.py", line 3675, in CRT_vectors
        a = CRT_basis(moduli)
            ^^^^^^^^^^^^^^^^^
      File "/Users/runner/work/sage/sage/src/sage/arith/misc.py", line 3641, in CRT_basis
        raise ValueError('moduli must be coprime')
    ValueError: moduli must be coprime
**********************************************************************

Environment

• OS: Linux
• Sage Version: latest develop

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[yyyyx4]

Related or possibly duplicate: #32487

[DaveWitteMorris]

I am not a number theorist, but I think the following is a reasonable construction of a CRT_basis for non-coprime moduli, because it should be easy to code and seems to be reasonably efficient.

We have moduli m_1,m_2,...,m_n.
Let e_1 = 1. For i > 1, let
M_i = lcm(m_1,m_2,...,m_{i-1})
and
d_i = gcd(M_i, m_i).
Now choose e_i to be a multiple of M_i/d_i that is congruent to 1 modulo m_i/d_i.
Finally, let
a_i = e_i * (1 - e_{i+1}) * (1 - e_{i+2}) * ... * (1 - e_n).
Then [a_1, a_2, ..., a_n] is the desired CRT_basis.

This means that the solution to the CRT problem with residues r_1,r_2,...,r_n is
sum(a_i * r_i for i in range(1, n+1))
(if a solution exists).

See the following comment for a justification of this CRT basis.

[DaveWitteMorris]

Justification of the above formula for a CRT_basis.

Let's see a particular solution of the CRT problem with just two residues a and b and two moduli m and n. Let d = gcd(m,n). Let e be a multiple of m/d, such that e is congruent to 1 modulo n/d. Then a solution to the CRT problem is given by
x := a * (1 - e) + e * b.

Proof. By simple algebra, we have
x = a + (b - a) * e.
Since there is a solution to the CRT problem, we know that b - a is divisible by d.
Note that the definition of e implies d * e = 0 (mod m), so
x = a + [(b - a)/d] * [d * e] = a + [(b - a)/d] * 0 = a (mod m).
Similarly, since d * e = d (mod n), we have
x = a + [(b - a)/d] * [d * e] = a + [(b - a)/d] * d = a + (b - a) = b (mod n).
QED

Now, we can justify the formula.
By induction, we can assume that if we let
a_i' = e_i * (1 - e_{i+1}) * (1 - e_{i+2}) * ... * (1 - e_{n-1})
then [a_1', a_2', ..., a_{n-1}'] is a CRT basis modulo M_{n-1}, so
sum(a_i' * r_i for i in range(1, n)) is the correct residue modulo M_{n-1}.
Therefore, by the above solution to the two-residue case, we know that a solution to the problem modulo M_n is

    sum(a_i' * r_i for i in range(1, n)) * (1 - e_n)  +  e_n * r_n
       = sum(a_i * r_i for i in range(1, n))  +  e_n * r_n
       = sum(a_i * r_i for i in range(1, n + 1)).

[user202729]

While that's a step in improvement, I'd rather hiding the feature behind a flag allow_non_coprime=True so that caller won't accidentally give wrong result.

[DaveWitteMorris]

Yes, I agree that a flag should be added to the CRT_basis method (and I think the default should be False). I don't think a flag is needed on the CRT_vectors method, but the result should be checked, and an error should be raised if formula did not give a correct solution to the CRT problem (which means that there does not exist a solution).

EDIT: I think it would be better to call the flag require_coprime_moduli (and then the default would be True).