Apologies in advance for what is probably a rather naïve question. I'm playing with a factoring algorithm in which CRT calculations are one of the bottlenecks. I have used an optimisation to the CRT calculation, which improves things slightly. I have never seen this optimisation mentioned in the literature, and was wondering why, as it is a very obvious one: Rather than solving:

x = r_{0} (mod m_{0})

x = r_{1} (mod m_{1})

...

x = r_{n} (mod m_{n})

we can solve

x-r_{0} = 0 (mod m_{0})

x-r_{0} = r_{1}-r_{0} (mod m_{1})

...

x-r_{0} = r_{n}-r_{0} (mod m_{n})

meaning one modular inversion can be avoided due to the 0 residue in the modified first congruence.

For example, in the case of just 2 congruences, this leads to:

x = r_{0} + |m_{0}^{-1}|_{m[SUB]1}[/SUB] m_{0} (r_{1}-r_{0}) (mod m_{0}m_{1})

rather than the usual:

x = |m_{1}^{-1}|_{m[SUB]0}[/SUB]m_{1}r_{0} + |m_{0}^{-1}|_{m[SUB]1}[/SUB]m_{0}r_{1} (mod m_{0}m_{1})

Do the disadvantages (initial extra addition plus extra subtraction per non-initial congruence, and the possible complications of (r

_{i}-r

_{0}) going negative) outweigh the advantages in general?

Just curious... (and apologies for using = rather than the congruence symbol, which I can't find!)