Alternate algorithms for Chinese remainder theorem

Question

I was teaching Discrete this semester and set the students loose on a system of linear congruences. One of them came up with this solution. Say $$ x \equiv 1 \textrm{ mod } 3 $$ $$ x \equiv 3 \textrm{ mod 4} $$ $$ x \equiv 2 \textrm{ mod } 5. $$

Then, we convert each congruence to a mod 60 congruence: $$ 20x \equiv 20 \textrm{ mod } 60 $$ $$ 15x \equiv 45 \textrm{ mod } 60$$ $$ 12x \equiv 24 \textrm{ mod } 60 $$ and sum them to get a single congruence $$ 47x \equiv 89 \textrm{ mod } 60.$$ The coefficient on the left will always be relatively prime to the mod, so this method always works.

This has to have been seen and studied before, right? I'm curious about the time complexity relative to the "standard" methods since we only have to calculate one multiplicative inverse. I imagine this is a loser on space complexity since that inverse is happening with the large modulus rather than the small ones. Any pointers to other discussions of this solution method, particularly complexity-wise?

Answer 1

If you're using the (extended) Euclidean algorithm to compute modular inverses mod $m$, then the time complexity is roughly $O((\log m)^2)$. So if $m = abc$ then you'd prefer to do $(\log a)^2 + (\log b)^2 + (\log c)^2$ work rather than $(\log a + \log b + \log c)^2$ work. In fact, it's a general rule of thumb in computational number theory that if the factorization is available, and you can apply the Chinese remainder theorem to perform your desired computation modulo the factors, then it will usually be cheaper to do it that way.