Thread: CRT optimisation? View Single Post
2016-03-30, 02:08   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by jasonp The problem I was thinking of was that in general (a mod b) mod c is not the same as (a mod c) mod b. So if your m0 was larger than m1, then (r1 - r0) mod m1 may not be the same as (r1 - (r0 mod m1)) mod m1. I could be overthinking it though.
to further point out this problem I decided to post an example:

(30 mod 5) mod 7 -> 0 mod 7
(30 mod 7) mod 5 -> 2 mod 5

all we did was change the order of the modulo operations and it changes what we get back.

I think jasonp is overthinking it if CRT is chinese remainder theorem as the mod is never done twice and if you subtract the same thing from two things that are congruent they stay congruent. in the two congruences you give ( unless you meant m0 in one of them) you can think of them as polynomials r1-r0 can be (m1*y+r1)-(m1*z+r2). though I still don't see how you can cross values mod the m's like that. if you remember that any value mod another number is always congruent to itself you can rewrite the second as the first.

Last fiddled with by science_man_88 on 2016-03-30 at 02:11