View Single Post
Old 2016-03-29, 13:12   #1
mickfrancis
 
Apr 2014
Marlow, UK

23·7 Posts
Default CRT optimisation?

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 = r0 (mod m0)
x = r1 (mod m1)
...
x = rn (mod mn)
we can solve
x-r0 = 0 (mod m0)
x-r0 = r1-r0 (mod m1)
...
x-r0 = rn-r0 (mod mn)
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 = r0 + |m0-1|m[SUB]1[/SUB] m0 (r1-r0) (mod m0m1)
rather than the usual:
x = |m1-1|m[SUB]0[/SUB]m1r0 + |m0-1|m[SUB]1[/SUB]m0r1 (mod m0m1)
Do the disadvantages (initial extra addition plus extra subtraction per non-initial congruence, and the possible complications of (ri-r0) going negative) outweigh the advantages in general?
Just curious... (and apologies for using = rather than the congruence symbol, which I can't find!)

Last fiddled with by mickfrancis on 2016-03-29 at 13:19 Reason: Formatting
mickfrancis is offline   Reply With Quote