Thread: CRT optimisation? View Single Post
 2016-03-29, 13:12 #1 mickfrancis   Apr 2014 Marlow, UK 23·7 Posts 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